Split Cuts in Fixed Integer Dimensions
Abstract
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 Θ(log N) can have split closures with at least 2N−1 facets, yet extension complexity Θ(log N). For the two-row system x=f+Rs, s≥0, x∈ℤ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 Op(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.
Related
- On solving integer bilevel optimization problems with a non-convex quadratic follower objective function using disjunctive cuts
- The average number of representations of an integer as a sum of three or more primes, over multiples of a fixed integer
- On the Krull dimensions of rings of integer-valued polynomials and polynomial rings
- Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension
- Applications of the fixed point theorem for mappings contracting perimeters of triangles: ODEs, PDEs, integer and difference equations
BibTeX
@misc{bhardwaj2026split,
title = {{Split Cuts in Fixed Integer Dimensions}},
author = {Avinash Bhardwaj and Vishnu Narayanan},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02169},
eprint = {2611.02169},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02169},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Split Cuts in Fixed Integer Dimensions
AU - Avinash Bhardwaj
AU - Vishnu Narayanan
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.02169
UR - https://arxiv.org/abs/2611.02169
AB - 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 Θ(log N) can have split closures with at least 2N−1 facets, yet extension complexity Θ(log N). For the two-row system x=f+Rs, s≥0, x∈ℤ^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.
ER -