We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász-Schrijver SDP operator \( \text{LS}_+\), with a particular focus on a search for relatively small graphs with high \( \text{LS}_+\)-rank (the least number of iterations of the \( \text{LS}_+\) operator on the fractional stable set polytope to compute the … Read more
We introduce a column elimination procedure for the capacitated vehicle routing problem. Our procedure maintains a decision diagram to represent a relaxation of the set of feasible routes, over which we define a constrained network flow. The optimal solution corresponds to a collection of paths in the decision diagram and yields a dual bound. The … Read more
In the known Interval Scheduling problem with Machine Availabilities (ISMA), each machine has a contiguous availability interval and each job has a specic time interval which has to be scheduled. The objective is to schedule all jobs such that the machines’ availability intervals are respected or to decide that there exists no such schedule. We … Read more
Supervalid inequalities are a specific type of constraints often used within the branch-and-cut framework to strengthen the linear relaxation of mixed-integer programs. These inequalities share the particular characteristic of potentially removing feasible integer solutions as long as they are already dominated by an incumbent solution. This paper focuses on supervalid inequalities for solving binary interdiction … Read more
We investigate some graph parameters dealing with biindependent pairs $(A,B)$ in a bipartite graph $G=(V_1\cup V_2,E)$, i.e., pairs $(A,B)$ where $A\subseteq V_1$, $B\subseteq V_2$ and $A\cup B$ is independent. These parameters also allow to study bicliques in general graphs. When maximizing the cardinality $|A\cup B|$ one finds the stability number $\alpha(G)$, well-known to be polynomial-time … Read more
We study the inefficiency of pure Nash equilibria in symmetric unweighted network congestion games. We first explore the impact of symmetry on the worst-case PoA of network congestion games. For polynomial delay functions with highest degree p, we construct a family of symmetric congestion games over arbitrary networks which achieves the same worst-case PoA of … Read more
Cut-strengthening techniques have a significant impact on the computational effectiveness of the Logic-based Benders’ decomposition (LBBD) scheme. While there have been numerous cut-strengthening techniques proposed, very little is understood about which techniques achieve the best computational performance for the LBBD scheme. This is typically due to implementations of LBBD being problem specific and thus, no … Read more
We consider semidefinite programming (SDP) approaches for solving the maximum satisfiabilityproblem (MAX-SAT) and the weighted partial MAX-SAT. It is widely known that SDP is well-suitedto approximate the (MAX-)2-SAT. Our work shows the potential of SDP also for other satisfiabilityproblems, by being competitive with some of the best solvers in the yearly MAX-SAT competition.Our solver combines … Read more
We study a two-stage stochastic combinatorial optimization problem that integrates fleet-sizing, assignment, routing, and scheduling problems. Although this problem has wide applicability, it arises in particular in the home healthcare industry where a service team of caregivers have to be assigned to patients and put in vehicle fleet that have to be routed amongst the … Read more
Let $A\in \mathbb{R}^{m\times n}\setminus \{0\}$ and $P:=\{x:Ax\le 0\}$. This paper provides a procedure to compute an upper bound on the following {\em homogeneous Hoffman constant} \[ H_0(A) := \sup_{u\in \mathbb{R}^n \setminus P} \frac{\text{dist}(u,P)}{\text{dist}(Au, \mathbb{R}^m_-)}. \] In sharp contrast to the intractability of computing more general Hoffman constants, the procedure described in this paper is entirely … Read more