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
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
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
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
We develop a few calculus rules to compute or lower bound the facial distance of a polytope. We illustrate our calculus rules on various popular polytopes. In particular, we provide a lower bound on the facial distance of the Birkhoff polytope. CitationWorking paper. Tepper School of Business. Carnegie Mellon UniversityArticleDownload View PDF
For integer activities, conditioning on the support makes a fixed-charge objective affine. If every support-conditioned cell is integral, an optimal solution is a vertex of its cell for arbitrary fixed charges and marginal rates. A totally unimodular constraint matrix with integral data guarantees this condition. This surviving property is weaker than the classical conclusions. A … Read more
The symmetry measure of a convex body \(S\subset\mathbb{R}^n\) is given by: \(\mathrm{sym}(S):=\max\{\alpha\ge0:\ \mathrm{there\ exists}\ x\in S\ \mathrm{such\ that}\ -\alpha(S-x)\subseteq S-x\}\), where such an \(x\) is called a Minkowski center. We prove that every convex body \(S\) admits a \(\sqrt{\frac{n}{\mathrm{sym}(S)}}\)-rounding of \(S\), namely, there exists an origin-centered ellipsoid \(E\) and a center \(c\) such that the … Read more
We give a simple example that disproves the following 2015 conjecture of Lacoste-Julien and Jaggi concerning the pyramidal width (aka facial distance): The pyramidal width of a set of vertices is non-increasing when another vertex is added (assuming that all previous points remain vertices). In contrast to the recent example by Zhao (arXiv:2607.29555), our counterexample … Read more
We address the classical Dantzig – Fulkerson – Johnson formulation of the symmetric metric Traveling Salesman Problem and study the integrality gap of its linear relaxation, namely the Subtour Elimination Problem (SEP). This integrality gap is conjectured to be 4/3. We prove that, when solving a problem on n nodes, if the optimal SEP solution … Read more
Classical Benders decomposition fails when the subproblem is a mixed-integer program, due to the absence of strong duality. We propose a novel class of dual-free indicator cuts that are applicable to all Benders-decomposable problems with a pure-integer master problem and mixed-integer linear programming (MILP) subproblems. These cuts are derived from the monotonicity property of the … Read more