The unpublished 1990 technical report reproduced here introduced the $t$-reinforced $k$-fence inequalities, the first facets of the acyclic subgraph polytope that are not rank inequalities: each simple $k$-fence induces $k-2$ of them, one for each $1\le t\le k-2$. The report proved this with the spectral method, using a coherent configuration and computer algebra. It went … Read more
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. In 1973, Chvátal asked whether 0/1 integer programs over polytopes of bounded Chvátal rank can be solved in polynomial time. For polyhedra of bounded Chvátal rank, integer feasibility is in NP ∩ coNP, so it … 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
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