Abstract: A three-way transportation polytope consists of nonnegative three-way arrays with prescribed sums along every coordinate line. We show that its geometry and the difficulty of finding its integer points are both controlled by one local quantity: the number of cells on a line that can be positive. The change happens between two and three. … Read more
Since its introduction in 2013, the dotted-board model has been widely used by the cutting and packing research community to tackle irregular packing problems. However, despite its popularity, little research has aimed at improving its performance when solved via off-the-shelf integer programming solvers, beyond the known strategy of merging pairwise incompatibility constraints into clique constraints … Read more
A rational polyhedron has Chvátal rank at most one if a single round of Chvátal-Gomory cuts yields its integer hull. For such polyhedra, integer feasibility is in NP ∩ coNP by a result of Boyd and Pulleyblank from the early 1980s, so it is unlikely to be NP-hard. Whether it is polynomial has remained open … Read more
An instance of the quadratic minimum spanning tree problem (QMSTP) is called linearizable if it can be rewritten as an instance of the linear minimum spanning tree problem in such a way that the objective function value is preserved at all feasible solutions. Previous work has shown that a sufficient condition for linearizability is that … Read more
We construct small extended formulations for nonnegative integer flows whose arc labels have a prescribed sum in a finite abelian group. For circulations, the formulation is a single integral network that combines cycles even when they lie in different components. This yields an O(Δn²) bound for strictly Δ-modular cographic integer hulls of translated cones, improving … Read more
This paper studies the single-machine problem of minimizing the weighted completion time variance (WCTV) and proposes a polynomially computable lower-bounding framework that generalizes the benchmark introduced by Nessah and Chu (2010). We first develop a generalized augmented-sequence decomposition that mathematically connects the weighted problem with the classical unweighted variance setting. Using this decomposition, we derive … Read more
The \(\textit{Colored Knapsack Problem}\) (ColKP) generalizes the classical Knapsack Problem by partitioning the items into color classes and requiring the selected items to admit an ordering in which consecutive items have different colors. The problem is weakly \(\mathcal{NP}\)-hard and admits two pseudo-polynomial dynamic programming (DP) algorithms proposed in the literature. These two DP algorithms have … Read more
Dynamic Discretisation Discovery (DDD) is a framework for solving a problem by iteratively solving and refining a relaxed version of the problem. DDD is the basis for state-of-the-art algorithms for various problems, including the continuous-time service network design problem (CTSNDP), which we study here. In the refinement step, such algorithms must identify conflicts in the … Read more
We show that every polytope $P\subseteq[0,1]^n$, and more generally every compact convex set, has Chv\’atal rank at most $12.22n^2+n\log_2 n+2n+4$. This improves the $O(n^2\log n)$ bound of Eisenbrand and Schulz and, together with the $\Omega(n^2)$ lower bound of Rothvo{\ss} and Sanit\`a, shows that the maximum Chv\’atal rank of a polytope in $[0,1]^n$ is $\Theta(n^2)$. More … Read more
State-of-the-art exact methods for the Maximum Cut problem are based on solving linear and semidefinite programming relaxations embedded into a branch-and-bound algorithm. For linear programming formulations, it was shown recently that it is thereby sufficient to enforce the integrality of the variables associated with the edges of a spanning tree. Our first contribution is to … Read more