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:\text{ there exists }x\in S\text{ 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 … 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
We study energy-efficient operation of underground train networks, where energy from regenerative braking is usable only if another train in the same electrically isolated subnetwork accelerates simultaneously. Timetabling models for this setting typically fix one velocity profile per leg and running time, which limits the matching of braking and accelerating phases. We drop this assumption … Read more
The binary reflected Gray code orders the vertices of the unit hypercube along a Hamiltonian path in which consecutive vertices differ in exactly one coordinate. While Gray codes have been extensively studied from a combinatorial perspective, much less is known about the polyhedral structure of convex hulls of contiguous subpaths of this order. This paper … Read more
We prove that computing a shortest monotone path to the optimum of a linear program over a simple polytope is NP-hard, thus resolving a 2022 open question of De Loera, Kafer, and Sanit\`{a}. As a consequence, finding a shortest sequence of pivots to an optimal basis with the simplex method is NP-hard. In fact, we … Read more