Metraipolis › archive › dc_4bf0fcd85a8d

Split Cuts in Fixed Integer Dimensions — arXiv:2611.02169

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.02169
License (as archived)
CC0-1.0
Archived
2026-11-03T11:32:24.692Z
SHA-256 of the archived text
1277436a28910ff89e6ff4cd87f7213cb70b7f76837634c2ab4d64a7e2637634
Stable URL of this page
https://metraipolis.com/documento/dc_4bf0fcd85a8d

How to cite

Split Cuts in Fixed Integer Dimensions — arXiv:2611.02169 — arXiv (en), https://arxiv.org/abs/2611.02169 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4bf0fcd85a8d (Metraipolis archive dc_4bf0fcd85a8d, sha256 1277436a28910ff89e6ff4cd87f7213cb70b7f76837634c2ab4d64a7e2637634)
BibTeX
@misc{dc4bf0fcd85a8d,
  title = {Split Cuts in Fixed Integer Dimensions — arXiv:2611.02169},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.02169},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4bf0fcd85a8d; sha256 1277436a28910ff89e6ff4cd87f7213cb70b7f76837634c2ab4d64a7e2637634},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02169. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study how many split cuts, which include the Gomory mixed-integer cuts, are needed to reach the integer hull, and how large split closures can be. In every fixed dimension, a rational pure-integer polytope admits a polynomial-time constructible split proof of its integer hull with polynomial total encoding length; consequently, its full split rank is polynomial in the input length. This establishes the split-rank conjecture of Basu, Conforti, Di Summa, and Jiang for bounded pure-integer polyhedra in fixed dimension. Central to our approach is a preservation result: in arbitrary pure-integer dimension, an inequality whose violating points map, under an integer-affine map, into the interior of a planar lattice-free polyhedron has a polynomial split proof retaining every point already satisfying it. Whereas Chvátal--Gomory closures have polynomial-size inequality descriptions in fixed dimension, split closures need not: tetrahedra of input length $\Theta(\log N)$ can have split closures with at least $2N-1$ facets, yet extension complexity $\Theta(\log N)$. For the two-row system $x=f+Rs$, $s\ge0$, $x\in\mathbb Z^2$ of input length $L$, the split closure has an exact extended formulation with $O(L)$ inequalities and auxiliary variables; this bound is tight. Separation over the split closure is polynomial-time in fixed total dimension. Finally, for mixed-integer feasible rational polytopes with fixed integer dimension $p$ and any continuous dimension, we maximize a primitive integral objective on the integer variables with $O_p(G+1)$ split cuts, each removing a current optimal LP vertex, until an optimal vertex is mixed-integer feasible; here $G$ is the integrality gap of the LP relaxation, rounded down.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2611.02169 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:04:22.256Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).