betaFeedback

WorksMathematics

Split Cuts in Fixed Integer Dimensions

Abstract

We study how many split cuts are needed to reach the integer hull, and how large split closures can be. In every fixed dimension, a rational pure-integer polyhedron 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 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 affine map with integer coefficients, into the interior of a planar lattice-free polyhedron has a polynomial split proof retaining every point 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)Θ(\log N) can have split closures with at least 2N−12N-1 facets, yet extension complexity Θ(log⁡N)Θ(\log N). For the system x=f+Rsx=f+Rs, s≥0s\ge0, x∈Z2x\in\mathbb Z^2 of input length LL, the split closure has an exact extended formulation with O(L)O(L) inequalities and auxiliary variables; this bound is tight. Separation over the split closure is polynomial-time in fixed total dimension. Finally, on mixed-integer feasible rational polytopes with fixed integer dimension pp and arbitrary continuous dimension, we optimize a primitive integral objective on the integer variables using Op(G+1)O_p(G+1) split cuts. Each cut removes a current optimal LP vertex, and the algorithm returns an optimal LP vertex that is mixed-integer feasible. GG is the integrality gap of the LP relaxation, rounded down.

Introduction

Split cuts are among the most useful cutting planes in integer programming. The Gomory mixed-integer and mixed-integer rounding cuts that modern solvers generate routinely are split cuts, and much of the theory of cutting planes is, in one way or another, a study of what split cuts can and cannot do. The idea behind them is simple. In a mixed-integer linear program, a linear function with integer coefficients involving only the integer variables takes an integer value at every feasible point, and so it never lies strictly between two consecutive integers. For such a function ℓ\ell and an integer kk, every feasible point therefore satisfies the split disjunction ℓ(x)≤k\ell(x) \le k or ℓ(x)≥k+1\ell(x) \ge k+1. Taking the convex hull of the points of the linear programming (LP) relaxation that satisfy either inequality can remove part of the relaxation without losing a single feasible point. Every linear inequality valid for this hull is a split cut, and the split closure is the intersection of these hulls over all split disjunctions, each applied to the same relaxation.

Two questions about split cuts motivate this paper. The first concerns the split closure itself: when only a few variables are integer, how many linear inequalities are needed to describe it, and can far fewer suffice if we allow additional continuous variables and then project? The second concerns sequences of cuts. Here the cuts are added one at a time, each derived from a split disjunction of the current relaxation, and we ask how many are needed to reach the integer hull, the convex hull of the integer feasible points. For optimization one may ask for more, namely that every cut remove a current optimal LP vertex.

Our main result answers the second question for pure-integer problems in fixed dimension. Basu, Conforti, Di Summa, and Jiang [12] conjectured that the split rank of a rational pure-integer polyhedron is polynomial in its input length, and noted that even dimension three was open. We show that, in every fixed dimension, the integer hull of a rational polyhedron is reached by a sequence of split cuts that can be constructed in polynomial time and has polynomial total encoding length (Theorem 1.4); polynomially many rounds of the split closure therefore suffice. Central to our approach is a preservation property: certain inequalities can be derived by split cuts without cutting off a single point, integer or fractional, that already satisfies them (Theorem 1.5). This preservation lets us apply induction on lower-dimensional sections while retaining the points contributed by the other sections.

The answer to the first question is rather different. Whereas Chvátal–Gomory closures have polynomial-size descriptions in fixed dimension [14], split closures need not: in dimension three we construct tetrahedra whose split closures have exponentially many facets in the input length, although their extension complexity is only linear in it (Theorem 1.1). For two-row systems the split closure always has an extended formulation of size linear in the input length (Theorem 1.2). We also give polynomial-time separation over the split closure when the total dimension is fixed, and a strong split-cut algorithm whose number of cuts depends only on the number of integer variables and the objective gap (Theorems 1.6 and 1.7).

Split cuts and notation

Let P⊆RdP \subseteq\mathbb{R}^d be a rational polyhedron, and let I⊆{1,…,d}I \subseteq\{1,\ldots,d\} index the coordinates designated integer; the mixed-integer feasible points of PP are those x∈Px \in P with xi∈Zx_i \in\mathbb{Z} for every i∈Ii \in I. Put ZId={π∈Zd:πj=0 for j∉I}\mathbb{Z}_I^d = \{\pi\in\mathbb{Z}^d : \pi_j = 0\text{ for }j \notin I\}. For π∈ZId∖{0}\pi\in\mathbb{Z}_I^d \setminus\{0\} and k∈Zk \in\mathbb{Z}, we call {x∈Rd:k<πTx<k+1}\{x \in\mathbb{R}^d : k < \pi^\mathsf{T}x < k+1\} the open split strip and {x∈Rd:k≤πTx≤k+1}\{x \in\mathbb{R}^d : k \le\pi^\mathsf{T}x \le k+1\} the closed split strip. No mixed-integer feasible point lies in the open strip, so each satisfies πTx≤k\pi^\mathsf{T}x \le k or πTx≥k+1\pi^\mathsf{T}x \ge k+1, and the convex hull of the points of PP satisfying at least one of these branches is

Pπ,k=conv⁡((P∩{πTx≤k})∪(P∩{πTx≥k+1})).P^{\pi,k}=\operatorname{conv}\bigl((P\cap\{\pi^\mathsf{T}x\le k\})\cup(P\cap\{\pi^\mathsf{T}x\ge k+1\})\bigr).

A split cut is any linear inequality valid for this hull, and the split closure is

SC⁡I(P)=⋂π∈Zd∖{0}, k∈ZPπ,k.(1)\operatorname{SC}_{I}(P)=\bigcap_{\substack{\pi\in\mathbb{Z}^{d}\setminus\{0\},\ k\in\mathbb{Z}}}P^{\pi,k}. \tag*{(1)}

We write SC⁡(P)\operatorname{SC}(P) when all variables are integer, and set SC⁡∅(P)=P\operatorname{SC}_{\varnothing}(P)=P. For any polyhedron Q⊆RdQ\subseteq\mathbb{R}^{d}, we write QI=conv⁡(Q∩Zd)Q_{I}=\operatorname{conv}(Q\cap\mathbb{Z}^{d}) for its integer hull. In the pure-integer case a single round of the split closure need not reach PIP_{I}, since convexification can put fractional points back inside the removed strip, as Figure 1 shows.

Removing an integer-free strip and taking the convex hull

Figure 1. Removing an integer-free strip and taking the convex hull creates a new edge, but leaves fractional points inside the strip. The dots mark the integer lattice.

Throughout, input length means the total binary encoding length of the supplied data, and a polyhedron is supplied by rational linear inequalities unless another representation is specified; a positive integer NN takes O(log⁡(N+1))O(\log(N+1)) bits to write. We keep counts of inequalities and variables separate from total encoding length, which also accounts for their coefficients.

A polytope is a bounded polyhedron, and we write R+=[0,∞)\mathbb{R}_{+}=[0,\infty) and Z+=Z∩R+\mathbb{Z}_{+}=\mathbb{Z}\cap\mathbb{R}_{+}. An integer vector is primitive if the greatest common divisor (gcd) of its coordinates is one. An affine map with integer coefficients, including its constant terms, maps integer points to integer points. A unimodular matrix is an integer matrix of determinant ±1\pm1, so that the corresponding change of coordinates preserves the integer lattice. Finally, {a}=a−⌊a⌋\{a\}=a-\lfloor a\rfloor denotes the fractional part of a∈Ra\in\mathbb{R}, and subscripts on O(⋅)O(\cdot) and poly⁡(⋅)\operatorname{poly}(\cdot) indicate the parameters on which the constants or the polynomial may depend.

Split-closure formulations

Cook, Kannan, and Schrijver [21] proved that split closures are rational polyhedra, and Vielma [53] gave a constructive finite description. For Chvátal–Gomory closures much more is known: Bockmayr and Eisenbrand [14] showed that, in fixed dimension, they have inequality descriptions of size polynomial in the input length. Whether the same holds for split closures is a question that Dash [26] attributes to Eisenbrand, and Basu, Conforti, Di Summa, and Jiang [10] answered it positively in the plane.

In dimension three the answer is negative, as our tetrahedral family shows. Perhaps surprisingly, the split closures in this family nevertheless have small extended formulations. Recall that a linear extended formulation of a polyhedron is a linear system in the original variables and auxiliary continuous variables whose projection onto the original variables is that polyhedron. Its size is the number of inequalities, equations not being counted, and the minimum size is the extension complexity xc⁡\operatorname{xc} [55].

Theorem 1.1. *For every integer N≥2N\ge2, there is a rational tetrahedron PN⊆R3P_{N}\subseteq\mathbb{R}^{3} with an inequality description of total encoding length Θ(log⁡N)\Theta(\log N) whose split closures SC⁡(PN)\operatorname{SC}(P_{N}) and SC⁡{1,2}(PN)\operatorname{SC}_{\{1,2\}}(P_{N}) each

have at least 2N−12N - 1 facets. Both closures have extension complexity Θ(log⁡N)\Theta(\log N) and admit exact rational extended formulations with O(log⁡N)O(\log N) inequalities and auxiliary variables, constructible in time polynomial in log⁡N\log N with polynomial total encoding length.

The idea behind Theorem 1.1 is geometric. The supporting hyperplanes of these facets meet an affine plane in tangents to a parabola, and all the inequalities needed for the closures fall into a constant number of families whose coefficients are quadratic functions of an integer parameter. Bogomolov, Fiorini, Maksimenko, and Pashkovich [16] gave small extended formulations for polygons whose vertices lie on a parabola, and these yield a small formulation for each family. The mixed-integer example also answers, negatively, a question discussed by Kalantarzadeh [41 Section 1.3]: whether split closures with two integer variables and one continuous variable always have polynomial-size inequality descriptions in the original variables.

A linear bound on formulation size also holds for the following system of two affine equations, with two coordinates designated integer and any number of nonnegative continuous variables.

Theorem 1.2. Let n≥0n \ge0 be arbitrary, let f∈Q2f \in\mathbb{Q}^{2} and R∈Q2×nR \in\mathbb{Q}^{2 \times n}, and let LL be the total binary encoding length of (f,R)(f, R). Define

Q(f,R)={(x,s)∈R2×R+n:x=f+Rs}.Q(f, R) = \{(x,s) \in\mathbb{R}^{2} \times\mathbb{R}_{+}^{n} : x = f + Rs\}.

With only x1,x2x_1, x_2 designated integer, one can construct an exact rational linear extended formulation of the split closure of Q(f,R)Q(f, R) with O(L)O(L) inequalities and auxiliary variables, uniformly in nn. The construction time and total encoding length are polynomial in $L.

This bound cannot be improved in general: already for n=3n = 3, there are examples requiring Ω(L)\Omega(L) inequalities in every extended formulation of their split closures. The proof first selects split disjunctions sufficient to define the closure and groups their normal vectors into arithmetic progressions. Within each progression, either the cuts at the endpoints suffice, or one additional split cut makes redundant all cuts sufficiently far from the endpoints. The remaining intervals admit the same parabolic formulations as in Theorem 1.1, and bounding the sum of their sizes yields the linear bound.

To pass from Q(f,R)Q(f, R) to a general inequality system, we use a result of Andersen, Cornuéjols, and Li [1], by which the split closure is the intersection of the split closures of the relaxations obtained by retaining maximal linearly independent sets of constraint rows. Applying our formulation to each of these relaxations yields the following bound.

Theorem 1.3. Let P={x∈Rd:Ax≥b}P = \{x \in\mathbb{R}^{d} : Ax \ge b\} be a rational polyhedron, where AA has mm rows and rank rr. Let I⊆{1,…,d}I \subseteq\{1,\ldots,d\} index the coordinates designated integer, with ∣I∣≤2|I| \le2, and let LL be the total input length of (A,b,I)(A,b,I). There is an absolute polynomial pp such that an exact rational linear extended formulation of SC⁡I(P)\operatorname{SC}_{I}(P) is constructible with total encoding length and running time at most (mr)p(L)\binom{m}{r}p(L).

The construction is therefore polynomial-time whenever either dd or the difference m−rm-r is fixed. Since a full-dimensional simplex has a facet description with m=d+1m = d + 1 and r=dr = d, simplices are covered even when dd varies.

The restriction to two integer variables can also be relaxed for a polyhedron defined by inequalities with linearly independent normal vectors. Let VV be its lineality space, the set of directions along which translation leaves the polyhedron unchanged, and consider the lattice of integer vectors that are supported on the integer coordinates and orthogonal to VV. If this lattice has rank at most two, then the split closure has an extended formulation constructible in polynomial time with polynomial total encoding length. This allows any number of integer variables and does not fix the ambient dimension.

Split proofs

A split proof starts from the input relaxation and adds one split cut at a time, each justified by a specified split disjunction of the current relaxation; earlier cuts are never discarded. A split proof of an inequality ends with a relaxation on which that inequality is valid. Its length is the number of cuts, and its encoding includes the cut inequalities together with their split disjunctions. Nothing in this definition requires a cut to remove an optimal LP vertex. When we do impose this, we call a sequence of split cuts, or a split proof, strong for a prescribed objective: every cut removes a vertex that is optimal for that objective over the current relaxation, the algorithm being free to choose among tied optimal vertices. The adjective weak, used in contrast with strong, indicates that the requirement is not imposed. The distinction is the one between cutting-plane proofs and cutting-plane algorithms in [12 Definitions 1.3 and 1.6], where an algorithm chooses a current optimal solution and adds a cut removing it.

For a pure-integer polyhedron PP, the full split rank is the least rr with SC⁡r(P)=PI\operatorname{SC}^{r}(P)=P_I, where SC⁡0(P)=P\operatorname{SC}^{0}(P)=P and SC⁡r+1(P)=SC⁡(SC⁡r(P))\operatorname{SC}^{r+1}(P)=\operatorname{SC}(\operatorname{SC}^{r}(P)); if no such rr exists, the rank is infinite. Basu, Conforti, Di Summa, and Jiang [12 Section 4] conjecture that the split rank of a rational pure-integer polyhedron is polynomially bounded in its input length, and note that this was open even in dimension three. The following theorem establishes the conjecture in every fixed dimension.

Theorem 1.4. Fix dd. Let P⊆RdP\subseteq\mathbb{R}^{d} be a rational polyhedron with all coordinates designated integer, and let PI=conv⁡(P∩Zd)P_I=\operatorname{conv}(P\cap\mathbb{Z}^{d}), possibly empty or lower-dimensional. One can construct in polynomial time a split proof ending exactly at PIP_I, with total binary encoding length polynomial in the input length. The full split rank of PP is also polynomially bounded in the input length. The polynomial may depend on dd.

Bounds on rank follow from bounds on proof length by monotonicity. If QjQ_j denotes the relaxation after jj proof cuts, then

SC⁡j(P)⊆Qj⟹SC⁡j+1(P)⊆SC⁡(Qj)⊆Qj+1,\operatorname{SC}^{j}(P)\subseteq Q_j\quad\Longrightarrow\quad\operatorname{SC}^{j+1}(P)\subseteq\operatorname{SC}(Q_j)\subseteq Q_{j+1},

where the last inclusion holds because the next inequality is a split cut of QjQ_j. Every iterate retains PIP_I, so a proof ending at Qk=PIQ_k=P_I gives SC⁡k(P)=PI\operatorname{SC}^{k}(P)=P_I, which bounds the rank in terms of the binary input length. The resulting description of the hull also permits polynomial-time optimization of any supplied rational linear objective. This is, of course, already possible by fixed-dimensional integer programming; what the theorem adds is a short split proof of the entire hull.

Let us describe the idea of the proof. We derive the defining inequalities of the integer hull one at a time, so consider one of them, written as h≤0h\leq0 with hh affine and with integer coefficients. First suppose PP is bounded and has points on both sides of h=1/2h=1/2. The polytope C=P∩{h≥1/2}C=P\cap\{h\geq1/2\} contains no integer point. We reduce CC to its face h=1/2h=1/2 while retaining that face. Each step extends to PP while retaining all points with h≤1/2h\leq1/2, and the final split h≤0h\leq0 or h≥1h\geq1 proves the desired inequality.

To reduce CC to this face, flatness gives an integer direction in which only a constant number of sections at integer values can be nonempty. One might hope to treat the sections separately, but taking the convex hull with the other sections can bring back points already removed. We control this effect by bounding 2h−12h-1 on each section and interpolating these bounds to obtain a concave piecewise-linear function. Induction lets us lower each bound while retaining the points contributed by the other sections. A complete pass decreases the upper bound by a fixed factor; after polynomially many passes, a split on 2h−12h-1 leaves exactly the desired face. Integer-free polytopes are refuted by first reducing to a section with one integer coordinate fixed and then using induction.

For an unbounded PP, we first project along any recession direction on which hh is constant. This reduces dimension, and every integer point of the projection has an integer lift to PP. When no such direction remains, P∩{h≥1/2}P \cap\{h \ge1/2\} is bounded, so the preceding construction applies. The proof thus uses induction on dimension for both the sections and the recession directions.

For this argument to apply recursively, the split cuts on a section must retain the points contributed by the other sections, fractional ones included. The preservation property we need comes from a result of independent interest. A planar polyhedron is lattice-free if its interior contains no integer point. Suppose that every point violating an inequality h≤0h \le0 maps, under two affine functions with integer coefficients, into the interior of such a polyhedron. The following theorem then gives a short split proof of the inequality, even when the original polytope has arbitrarily many variables.

Theorem 1.5. Let nn be arbitrary and let P⊆RnP \subseteq\mathbb{R}^n be a rational polytope with all coordinates designated integer. Suppose the input supplies an affine map u:Rn→R2u : \mathbb{R}^n \to\mathbb{R}^2 with integer coefficients, a rational affine function hh, and a full-dimensional rational lattice-free polyhedron K⊆R2K \subseteq\mathbb{R}^2 such that

h(z)>0  ⟹  u(z)∈int⁡K(z∈P).h(z) > 0 \implies u(z) \in\operatorname{int} K \qquad(z \in P).

One can construct a split proof ending exactly at P∩{h≤0}P \cap\{h \le0\}, with construction time, cut count, and total binary encoding length polynomial in (P,u,h,K)(P,u,h,K). Every original point satisfying the inequality, including fractional points, is retained.

The hypothesis explains why h≤0h \le0 is valid for the integer points of PP: their images under uu are integer points, whereas every violating point maps into an interior containing no integer point. The theorem turns this geometric reason for validity into a polynomially encoded split proof. When KK is a strip between consecutive integer hyperplanes, a single split cut suffices. A general planar lattice-free polyhedron, however, need not fit inside such a strip, and the content of the theorem is that a polynomial sequence of split cuts is still enough.

Let us describe some consequences of Theorem 1.5. First, consider the two-row system Q(f,R)Q(f,R) of Theorem 1.2. Suppose a pure-integer rational polytope P⊆RnP \subseteq\mathbb{R}^n is supplied with an affine map u:P→R2u : P \to\mathbb{R}^2 with integer coefficients and a rational affine map ss such that

s(z)≥0,u(z)=f+Rs(z)(z∈P).s(z) \ge0,\qquad u(z) = f + Rs(z) \qquad(z \in P).

Thus (u(z),s(z))∈Q(f,R)(u(z),s(z)) \in Q(f,R). We can enforce membership in the mixed-integer hull of Q(f,R)Q(f,R), the convex hull of its points with x∈Z2x \in\mathbb{Z}^2, by split cuts in the original variables zz. The construction time and total proof encoding are polynomial in the supplied data, without fixing nn or the number of components of ss.

The same theorem lets us replace a cross cut by split cuts. Here a cross cut is an inequality valid on each of the four subsets obtained by choosing one branch from each of two split disjunctions. More generally, a supplied proof using cross cuts, the mixed-integer hull operations above, or the planar lattice-free certificates of Theorem 1.5 can be converted into a split proof in polynomial time. The input encoding includes the maps and disjunctions defining each step.

In fixed dimension, we can also construct the planar lattice-free polyhedron needed in the theorem. Let PP be a pure-integer rational polytope and let uu consist of two supplied affine functions with integer coefficients. We can derive any inequality valid at every point of PP with u(z)∈Z2u(z) \in\mathbb{Z}^2, retaining every point that already satisfies it. We can also obtain exactly

U=conv⁡{z∈P:u(z)∈Z2}.U = \operatorname{conv}\{z \in P : u(z) \in\mathbb{Z}^2\}.

If a rational polytope G⊆PG \subseteq P is to be retained, the construction instead gives conv⁡(G∪U)\operatorname{conv}(G \cup U). These constructions take polynomial time using classical fixed-dimensional integer programming and integer-hull algorithms [22, 39, 45]. This is the form of preservation that allows the induction to treat one section while retaining the points contributed by the others.

Separation and optimization

A split closure may have many facets even when membership can be tested efficiently. Given a rational point, strong separation means either certifying that the point belongs to the split closure or returning a linear inequality valid for the closure and violated by that point. This use of “strong” has nothing to do with requiring each cut in a sequence to remove a current optimal LP vertex. We obtain polynomial-time separation when the total number of variables is fixed.

References

  1. [1]Kent Andersen, Gérard Cornuéjols, and Yanjun Li. Split closure and intersection cuts. Mathematical Programming, 102(3):457–493, 2005.
  2. [2]Cinar Ari and Robert Hildebrand. Bounded integer quadratic programming through parallelepiped covers and discrete convex optimization. arXiv preprint arXiv:2609.17889, 2026. URL https://arxiv.org/abs/2609.17889.
  3. [3]Egon Balas. Intersection cuts—a new type of cutting planes for integer programming. Operations Research, 19(1):19–39, 1971.DOI
  4. [4]Egon Balas and Anureet Saxena. Optimizing over the split closure. Mathematical Programming, 113 (2):219–240, 2008.
  5. [5]Egon Balas, Matteo Fischetti, and Arrigo Zanette. On the enumerative nature of Gomory’s dual cutting plane method. Mathematical Programming, 125(2):325–351, 2010.DOI
  6. [6]Wojciech Banaszczyk, Alexander E. Litvak, Alain Pajor, and Stanislaw J. Szarek. The flatness theorem for nonsymmetric convex bodies via the local theory of Banach spaces. Mathematics of Operations Research, 24(3):728–750, 1999.DOI
  7. [7]Amitabh Basu and Hongyi Jiang. Two-halfspace closure. Mathematical Programming, 197:411–426, 2023.arxiv.org/abs/2006.11587
  8. [8]Amitabh Basu, Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli. Maximal lattice-free convex sets in linear subspaces. Mathematics of Operations Research, 35(3):704–720, 2010.
  9. [9]Amitabh Basu, Robert Hildebrand, and Matthias Köppe. The triangle closure is a polyhedron. Mathematical Programming, 145(1–2):19–58, 2014.arxiv.org/abs/1111.1780
  10. [10]Amitabh Basu, Michele Conforti, Marco Di Summa, and Hongyi Jiang. Split cuts in the plane. SIAM Journal on Optimization, 31(1):331–347, 2021.arxiv.org/abs/2003.05022
  11. [11]Amitabh Basu, Michele Conforti, Marco Di Summa, and Hongyi Jiang. Complexity of branch-and-bound and cutting planes in mixed-integer optimization—II. Combinatorica, 42:971–996, 2022.
  12. [12]Amitabh Basu, Michele Conforti, Marco Di Summa, and Hongyi Jiang. Complexity of branch-and-bound and cutting planes in mixed-integer optimization. Mathematical Programming, 198(1):787–810, 2023.
  13. [13]Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, and Robert Robere. Stabbing planes. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics, pages 10:1–10:20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018.
  14. [14]Alexander Bockmayr and Friedrich Eisenbrand. Cutting planes and the elementary closure in fixed dimension. Mathematics of Operations Research, 26(2):304–312, 2001.DOI
  15. [15]Merve Bodur, Sanjeeb Dash, and Oktay Günlük. Cutting planes from extended LP formulations. Mathematical Programming, 161:159–192, 2017.DOI
  16. [16]Yuri Bogomolov, Samuel Fiorini, Aleksandr Maksimenko, and Kanstantsin Pashkovich. Small extended formulations for cyclic polytopes. Discrete & Computational Geometry, 53(4):809–816, 2015.DOI
  17. [17]Alberto Caprara and Adam N. Letchford. On the separation of split cuts and related inequalities. Mathematical Programming, 94(2–3):279–294, 2003.DOI
  18. [19]Michele Conforti, Marianna De Santis, Marco Di Summa, and Francesco Rinaldi. Scanning integer points with lex-inequalities: a finite cutting plane algorithm for integer programming with linear objective. 4OR, 19:531–548, 2021.arxiv.org/abs/1811.02345
  19. [20]William Cook, Collette R. Coullard, and György Turán. On the complexity of cutting-plane proofs. Discrete Applied Mathematics, 18(1):25–38, 1987.DOI
  20. [21]William Cook, Ravi Kannan, and Alexander Schrijver. Chvátal closures for mixed integer programming problems. Mathematical Programming, 47:155–174, 1990.DOI
  21. [22]William Cook, Mark Hartmann, Ravi Kannan, and Colin McDiarmid. On integer points in polyhedra. Combinatorica, 12(1):27–37, 1992.DOI
  22. [23]Gérard Cornuéjols and Vrishabh Patil. A hereditary property of cutting plane procedures. arXiv preprint arXiv:2609.02038, 2026. URL https://arxiv.org/abs/2609.02038.
  23. [24]Daniel Dadush and Samarth Tiwari. On the complexity of branching proofs. In 35th Computational Complexity Conference (CCC 2020), volume 169 of Leibniz International Proceedings in Informatics, pages 34:1–34:35. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020.arxiv.org/abs/2006.04124
  24. [25]Sanjeeb Dash. On the complexity of cutting-plane proofs using split cuts. Operations Research Letters, 38(2):109–114, 2010.
  25. [26]Sanjeeb Dash. Mixed integer rounding cuts and master group polyhedra. In Vašek Chvátal, editor, Combinatorial Optimization: Methods and Applications, volume 31 of NATO Science for Peace and Security Series D: Information and Communication Security, pages 1–32. IOS Press, 2011. URL https://www.math.uwaterloo.ca/~bico/bellairs/nato4.pdf. Preprint: IBM Research Report RC24521, 2008.
  26. [27]Sanjeeb Dash and Yatharth Dubey. On polytopes with linear rank with respect to generalizations of the split closure. Discrete Optimization, 51:100821, 2024.
  27. [28]Sanjeeb Dash, Oktay Gӧnülük, and Andrea Lodi. MIR closures of polyhedral sets. Mathematical Programming, 121:33–60, 2010.
  28. [29]Sanjeeb Dash, Santanu S. Dey, and Oktay Gӧnülük. On mixed-integer sets with two integer variables. Operations Research Letters, 39:305–309, 2011.DOI
  29. [30]Sanjeeb Dash, Santanu S. Dey, and Oktay Gӧnülük. Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra. Mathematical Programming, 135:221–254, 2012.DOI
  30. [31]Sanjeeb Dash, Oktay Gӧnülük, and Robert Hildebrand. Binary extended formulations of polyhedral mixed-integer sets. Mathematical Programming, 170:207–236, 2018.DOI
  31. [32]Santanu S. Dey and Quentin Louveaux. Split rank of triangle and quadrilateral inequalities. Mathematics of Operations Research, 36(3):432–461, 2011.arxiv.org/abs/0906.0887
  32. [33]Santanu S. Dey and Marco Molinaro. Theoretical challenges towards cutting-plane selection. Mathematical Programming, 170:237–266, 2018.arxiv.org/abs/1805.02782
  33. [34]Jean-Paul Doignon. Convexity in cristallographical lattices. Journal of Geometry, 3:71–85, 1973.DOI
  34. [35]Friedrich Eisenbrand and Gennady Shmonin. Parametric integer programming in fixed dimension. Mathematics of Operations Research, 33(4):839–850, 2008.arxiv.org/abs/0801.4336
  35. [36]Friedrich Eisenbrand, Samuel Fiorini, Lars Rohwedder, and Jiaye Wei. Polyhedral extended formulations that approximate the Gomory closure for packing problems. arXiv preprint arXiv:2607.09222, 2026. URL https://arxiv.org/abs/2607.09222.
  36. [37]Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, and Avi Wigderson. On the power and limitations of branch and cut. In 36th Computational Complexity Conference (CCC 2021), volume 200 of Leibniz International Proceedings in Informatics, pages 6:1–6:30. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021.
  37. [38]Dinakar Gade and Simge Küçükyavuz. Pure cutting-plane algorithms and their convergence. In Wiley Encyclopedia of Operations Research and Management Science. Wiley, 2013.DOI
  38. [39]Mark Evan Hartmann. Cutting Planes and the Complexity of the Integer Hull. PhD thesis, Cornell University, 1989.
  39. [40]Robert Hildebrand, Timm Oertel, and Robert Weismantel. Note on the complexity of the mixed-integer hull of a polyhedron. Operations Research Letters, 43(3):279–282, 2015.arxiv.org/abs/1412.2520
  40. [41]Sina Kalantarzadeh. Cuts in optimization and approximation: Generalized MIR cutting plane and integrality gap bounds for the planar multicut problem. Master of Mathematics thesis, Department of Combinatorics and Optimization, University of Waterloo, 2025. URL https://hdl.handle.net/10012/22484.
  41. [42]Ravindran Kannan and Achim Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM Journal on Computing, 8(4):499–507, 1979.DOI
  42. [43]Dabeen Lee. On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube. Discrete Optimization, 32:11–18, 2019.DOI
  43. [44]Arjen K. Lenstra, Hendrik W. Lenstra, Jr., and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982.
  44. [45]Hendrik W. Lenstra, Jr. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538–548, 1983.
  45. [46]Niels Lindner and Berenike Masing. On the split closure of the periodic timetabling polytope. Mathematical Programming, 215:325–367, 2026.
  46. [47]George L. Nemhauser and Laurence A. Wolsey. Integer and Combinatorial Optimization. Wiley, 1988.
  47. [48]José Neto. A simple finite cutting plane algorithm for integer programs. Operations Research Letters, 40:578–580, 2012.DOI
  48. [49]Francis J. Nourie and Enrique R. Venta. An upper bound on the number of cuts needed in Gomory’s method of integer forms. Operations Research Letters, 1:129–133, 1982.DOI
  49. [50]Jonathan H. Owen and Sanjay Mehrotra. A disjunctive cutting plane procedure for general mixed-integer linear programs. Mathematical Programming, 89:437–448, 2001.DOI
  50. [51]Thomas Rothvoß. The matching polytope has exponential extension complexity. Journal of the ACM, 64(6):41:1–41:19, 2017.
  51. [52]K. Spalding and A. P. Veselov. Conway river and Arnold sail. Arnold Mathematical Journal, 4:169–177, 2018.arxiv.org/abs/1801.10072
  52. [53]Juan Pablo Vielma. A constructive characterization of the split closure of a mixed integer linear program. Operations Research Letters, 35(1):29–35, 2007.DOI
  53. [54]Linچuan Wei. Integer quadratic programming in fixed dimension is polynomial-time solvable. Optimization Online preprint, September 14, 2026. URL https://optimization-online.org/2026/09/integer-quadratic-programming-in-fixed-dimension-is-polynomial-time-solvable/
  54. [55]Mihalis Yannakakis. Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences, 43(3):441–466, 1991.

Paper details

vlnc:W_mbsnmnxn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI’s ChatGPT

View statement
Looking for related papers…
Contents