WorksMathematics
A Polynomial Bound on Split Rank
Abstract
We prove that the split rank of a rational pure-integer polyhedron is polynomially bounded in its input length, resolving a conjecture of Basu, Conforti, Di Summa, and Jiang. If the defining system has dense binary encoding length , then split rounds suffice to reach the integer hull in arbitrary dimension.
Introduction
Let be a rational polyhedron with integer hull . Throughout, we assume without loss of generality that the defining inequalities of and and the target inequality have integer coefficients. A split , where and , has two branches, and . Every integer point satisfies one of them. An inequality valid on both branches in is a split cut for . One split round imposes all split cuts for the current relaxation. Starting from , write for the relaxation after rounds. The split rank of is the least integer such that . Schrijver proved that finitely many Chvátal–Gomory rounds suffice to reach [16 Theorem 2]. Since every Chvátal–Gomory cut is a split cut, the split rank is finite. When , Cook, Coullard, and Turán [10 Theorem 1] proved that a number of Chvátal cuts depending only on the dimension suffices to reduce to the empty set. For mixed-integer polyhedra, even one continuous variable can give infinite split rank [11 Example 2].
In the pure-integer case, every rational polyhedron in the plane has split rank at most two [3 Remark 3.15]. In dimension three, the rank can be arbitrarily large even when the integer hull is fixed. To see this, let be the triangle with vertices , , and . For a positive integer , let be the tetrahedron obtained by adjoining the apex . Every point of at positive height satisfies , , and . No integer pair satisfies these inequalities. Since the vertices of are integral, is the integer hull of . Conforti et al. showed that deriving on requires split rounds [9 Lemma 19]. The four inequalities defining take bits in total, so this family gives a lower bound linear in the input length. More generally, Conforti et al. characterize the integer hulls that admit rational relaxations of arbitrarily large split rank [8 Theorem 1].
Basu, Conforti, Di Summa, and Jiang [4 Section 4] conjectured that the split rank of a rational polyhedron is bounded by a polynomial in its input length, even when the dimension is part of the input. In [5], the authors established the conjecture in fixed dimension by constructing a split proof of polynomial total encoding length. The polynomial bound in [5] depends on the dimension. The following theorem bounds the number of split rank by a single polynomial when the dimension is part of the input.
Theorem 1. Let be a rational pure-integer polyhedron given by a system of linear inequalities of dense binary encoding length . The split rank of is .
A split round imposes all split cuts for the current relaxation. A split proof adds one cut at a time, and its length is the number of cuts it uses. For a polytope in , taking the convex hull over the two branches of each coordinate split in succession gives the integer hull in at most
Key words and phrases. Split rank, integer hull, split cuts, cutting planes. rounds [1]. This bound is tight [12]. Even a polytope in the cube defined by inequalities can have empty integer hull and split rank [14]. Yet some 0–1 systems require exponentially many individual split cuts to prove infeasibility [13]. In Section 4 we show that the round bound in Theorem 1 still holds when each cut and its split have encoding length polynomial in .
Idea of the proof
For the tetrahedron , deriving suffices to reach the integer hull. More generally, suppose , and let be a defining inequality of that is violated somewhere on . We call the height of . Since , and have the same recession cone [17]. Validity of on therefore gives for every . Hence is bounded above on .
Figure 1. The convex function is at most one at the vertices, hence throughout the polygon. Its tangent at is . On both branches of , , so the raised tangent cuts off the cap containing . The midpoint survives every cut from this split because it lies between the two marked branch points.
Let . We show that polynomially many split rounds suffice to halve the upper bound on . After halvings, for every in the current relaxation, so the branch contains no point of that relaxation. Thus the split gives in one further round. Section 3 bounds both the number of halvings and the number of rounds per halving uniformly over the defining inequalities of . Thus all these inequalities hold after the same polynomial number of rounds.
To see how one halving works, consider a bounded . Fix a point of height greater than . Around , we construct an ellipsoid small enough that every point in it still has positive height and satisfies for every defining inequality of . An integer point in the ellipsoid would therefore satisfy every defining inequality of and violate . Thus the ellipsoid contains no integer point. Banaszczyk’s theorem [2] then gives a split whose two branches stay a positive distance from , measured relative to the ellipsoid. The lower bound on this distance depends only on the dimension.
A point between the branches can still belong to their convex hull. To obtain a cut, we use a convex function of the height and the slacks of the defining inequalities. Its tangent at agrees with the function at . On either branch at nonnegative height, the distance bound gives a gap between the tangent and the function. This leaves room to raise the tangent and obtain an affine inequality that excludes whenever it violates the bound for the next round. Figure 1 illustrates this step. At heights at least , the upper bound on the function decreases in each round until it falls below a fixed lower bound. By then every remaining point has height less than . Figure 2 shows how repeating this halving gives the rank bound.

Figure 2. Proof of Theorem 1 for . Section 2 proves the halving step. Section 3 bounds both the number of halvings and the rounds per halving uniformly over the defining rows. For nonempty with , one halving with and suffices.
Halving the maximum violation
Let be bounded above on , with on . Suppose the current relaxation satisfies and on , where . We seek to derive by split cuts. If this bound already holds on , no further rounds are needed. Otherwise, is nonempty. For each defining inequality of , let be its shifted slack. Then on , so is defined even where the inequality is tight. For , is an integer, so is equivalent to .
Distance to the split branches
To bound the variation of on , we also need an upper bound on . When is bounded, every shifted slack has a finite maximum on . For an unbounded example, take and . Here , and the shifted slack of the row is unbounded. We can omit this row because already forces at every integer point satisfying the remaining inequalities. Lemma 1 shows that we can always retain a set of rows whose shifted slacks are bounded on and whose inequalities exclude every integer point with .
Lemma 1. There is a set such that is finite for each , and every satisfying for all has $g(z) \le 0.
Proof. Let , the set of directions such that for every and . Along each such direction, for every , since for all . Moreover, stays between and , so . Since is a rational polyhedral cone, it has a finite set of integer generators. Set , taking if . Retain the rows whose slack stays constant along , that is, .
For each , we have . Since for every , it follows that for every . As generates , we have for every . By the Minkowski–Weyl theorem, for some finite nonempty set . Thus for and . Since is affine, .
Let satisfy for every . For , we have , so for every . For , we have , so whenever
Choose a nonnegative integer at least as large as each of these finitely many lower bounds. Then satisfies every defining inequality of . Since and are integral, , where . As , we obtain .
Lemma 1 shows that the region where and for every contains no integer point. To find a split whose two branches stay away from a point of positive height, we first bound how far can move while remaining in this region. Let and consider with . The matrix has rows for and last row . For ,
If , each ratio in (1) has absolute value less than . Hence for every , and .
We now consider the images of the integer points in . For , each and is an integer. Thus the coordinate of corresponding to row is an integer multiple of , and its last coordinate is an integer multiple of . Two distinct points of differ in at least one coordinate. Their distance is therefore at least the smallest of these positive spacings. Hence is discrete. It is the additive group generated by the columns of , since is their linear combination with coefficients . Those same columns span over , so is a lattice spanning .
Suppose a point of were at distance less than from . That point has the form for some , so . By (1), for every and . Since is integral, implies . Thus satisfies every inequality indexed by , and Lemma 1 implies , a contradiction. Hence .
The bound measures the distance to the nearest lattice point. To construct a split, we need a direction in which lies between two consecutive parallel hyperplanes and stays a positive distance from both. We choose the direction from the dual lattice
For , every point of lies on one of the hyperplanes , . The distance from to the hyperplane indexed by is . Minimizing over yields the distance to the nearest hyperplane. For , Håstad [15] showed that one can choose so that the distance from to the nearest of these hyperplanes is at least . Banaszczyk [2, Theorem 2.3] improved the dependence of the denominator on from quadratic to linear. We use the following consequence of his theorem.
Lemma 2. Let be a lattice spanning a Euclidean space of dimension . For every , there is a nonzero such that
Proof. Suppose . By Banaszczyk [2, Theorem 2.3], there is a vector satisfying
Let be an integer nearest to . If , then , contrary to the second inequality. Thus , which also implies . The first inequality implies . Multiplying these bounds proves the claim.
For , choose a unit coordinate in which , with . Then belongs to , and
Lemma 2 determines a split in the original variables. Take and let satisfy the lemma. The vector is integral because each of its entries is the inner product of with a column of , and each column belongs to . Since , Lemma 2 implies that is not an integer. In particular, . Let . For on either branch of , the interval between and contains or . Thus . By Cauchy–Schwarz and Lemma 2,
where the last inequality uses and . Figure 3 illustrates the distances from to the lattice and to the nearer split branch.

Figure 3. From , the nearest point of is at distance (dotted), and the nearer branch of is at distance (solid). The ball of radius about contains no lattice point but meets the left branch.
To prove that a cut holds at a branch point with , we will use the point where the segment crosses . This point can lie between the branches, where (2) does not apply. On the entire section , however, the height term in (1) already suffices. For every with ,
since .
The halving bound
We use the distance estimates (2) and (3) to bound the gap between a convex function and its affine tangent at . This gap will allow us to raise the tangent while keeping it below the function on both split branches at nonnegative height and on the entire section . For with , let
where is the natural logarithm. Since , we have . Also, , so for every . Consequently,
The same applies at every halving because , , and the depend only on and .
Let be the affine tangent to at . For each among the shifted slacks and , let . Since , the change in from to is . The corresponding change in its tangent is , since the derivative of at is . Summing over , we obtain
These are the same relative changes that appear in (1): in particular, . Thus , the quadratic form of the Hessian of at evaluated on [6 Section 11.2]. To bound the tangent gap from below, it remains to compare with .
Let for . Since and , the minimum of is zero. On , we have , so Taylor’s theorem at zero implies . For , we have , so .
Let lie on either branch of the split , with . By (2), . Squaring and using (1), we obtain
If every , then for each . Summing these inequalities yields
If some , then . All other terms are nonnegative, so , since . In both cases the only property of the split branch used was the distance bound in (2). Thus, for every with ,
In particular, (6) also applies on the entire section , since (3) bounds the distance there by at least . We use this gap in successive split rounds to lower the upper bound on at points with . Once that upper bound falls below , (5) excludes every such point.
Lemma 3. If on , then on for .
Proof. Let . We seek an upper bound on that decreases with each round at points of height at least . The split in (2) is available when , where . To account for this threshold, let . Then when , and when . We prove by induction on that
For , this is the upper bound in (5). When , both terms on the left of (7) are nonpositive for every . When , (7) requires .
Assume (7) holds on , and let with satisfy
Since by (5), we must have . Thus by the definition of , and the split in (2) applies at . Since is affine, the tangent at to is .
Let lie on either branch of , with . Since , we have . By (2), , so (6) implies . Adding to both sides of yields
where the last inequality follows from the induction hypothesis (7). Thus we can raise the tangent by and still have on both branches at nonnegative height, where
The coefficients of may be irrational. Validity on both branches suffices here because every affine inequality valid on both branches holds on their closed convex hull. Section 4 constructs a rational cut for the same split that also excludes .
At , we have and , since . Hence
Thus violates , whereas every on either branch with satisfies
The bound also holds for every with , including points between the two branches. Indeed, (3) implies , so by (6). Since by (5) and , equation (8) implies
Now let lie on either branch with . Since , the segment contains a point with . If , then by (9), and affineness implies , contradicting . Thus on both branches at negative height as well. Together with (10), this proves that is a split cut for . For every with and
we have constructed a split cut for that excludes . Since satisfies every split cut for , every with satisfies
This proves the induction step.
Suppose satisfies . Since , we have . The lower bound in (5) and the upper bound in (7) therefore imply
Such a point can exist only if . Since , every satisfies , as illustrated in Figure 4.
Figure 4. In the normalized coordinates , the dashed line of slope passes through . When , the upper bound in (7) is steeper, so the shaded region satisfying (5) and (7) lies entirely in .
The rank bound
Lemma 3 bounds the number of split rounds needed to halve an upper bound on . To prove Theorem 1 for , we need two estimates for each defining inequality of that is violated on . The initial height determines how many halvings are needed to reach . The quantity in (5) determines how many rounds each halving takes. We bound both in terms of the input length . Let . The dense encoding counts every coefficient and right-hand side, including zeros, and each entry in the integer description of requires bits. If , then . If , then is either empty or consists of the unique point of , which is integral. In either case , so the split rank is zero. We may therefore assume . The dense encoding records coefficients and one right-hand side for each of the inequalities, so . In particular, .
Lemma 4. Suppose . Then has a finite description by inequalities with bits per coefficient, including the constant term. For each inequality in this description that is violated on , the maximum of on is finite. With and for the rows of Lemma 1, we have
If and , the same bounds hold for and $H_0=1.
Proof. We use a determinant bound three times. First, we bound the coordinates of the point and recession generators of . These bounds determine a box large enough that . Second, we use this description to express validity of an inequality as a system of linear inequalities in the coefficients of . Applying the determinant bound to this system bounds the coefficients of a defining description of . We then bound by evaluating each defining function on the point generators of . Third, we apply the determinant bound to . By Lemma 1, each retained slack is constant along every recession direction of , so its maximum is attained at a point generator of .
Let , where is an integer matrix and for some . We show that has a finite set of integer generators, each of whose coordinates requires at most
The cone may contain a line. To obtain cones generated by extreme rays, intersect with each coordinate orthant. In particular, for each , let
These cones cover , since every vector has a choice of coordinate signs. Each is pointed: if and both belong to , then for every , so . Let lie on an extreme ray of . Form from the rows for which and the rows for which . These are precisely the constraints defining that hold with equality at . Since and , we have . If the rank were smaller, the nullspace of would contain a vector linearly independent of . Then , and for sufficiently small , all remaining inequalities would still hold because they are strict at . Thus would be the midpoint of two points of outside its ray, contradicting extremality. Hence .
For , choose linearly independent rows of and let be the matrix with these rows. Since and has rank , its nullspace is the line spanned by . To find an integer vector on this line, let be the square matrix obtained by deleting column of , and define
To verify , consider any row of . Placing above produces a square matrix with two identical rows, so its determinant is zero. Expanding along the first row yields . Thus for every row of . Since has rank , some columns are linearly independent, so at least one determinant is nonzero. Thus is a nonzero integer vector in . Since , either or generates the ray containing .
Each row of is either a row of or a coordinate row , so every entry has absolute value at most . Each of the rows of therefore has Euclidean norm at most . Hadamard’s inequality bounds the absolute determinant by the product of these row norms. Hence
The binary length of , including its sign, is consequently at most , as required in (11). For , the positive and negative rays have generators and , respectively, so (11) also holds.
Finally, each is a pointed polyhedral cone, so it is generated by its finitely many extreme rays. Every belongs to some and is therefore a nonnegative combination of the generators chosen for that cone. Conversely, every chosen generator lies in , and contains all their nonnegative combinations. Taking the generators over the finitely many sign vectors therefore gives a finite generating set for satisfying (11).
By the Minkowski–Weyl theorem, has finite sets of point generators and recession generators such that
To bound their coordinates, apply (11) to the homogenized cone . From its integer generators, take for each with , and for each . The system defining has variables and bits per coefficient. Since , (11) bounds each generator coordinate by bits. As is a positive integer for each point generator, . Thus every vector in has infinity norm at most .
Suppose . Let , taking the second maximum to be zero if . For , we claim that
Let . By (12) and conic Carathéodory [17 Corollary 7.1i], for some , , and , with . The point
is integral by the first equality and belongs to by the second. Each remaining coefficient is less than one, so by the choice of . Thus and . Taking convex hulls proves the forward inclusion in (13).
Conversely, , and because [17]. Hence , proving (13).
By (12) and (13), an inequality is valid for if and only if
These inequalities define a cone in the variables . Each coordinate of is an integer of absolute value at most . The coordinate bound following (12) and the definition of imply that and for every . Thus each coefficient of this system has bits. By (11), this cone has a finite set of integer generators with bits per coordinate. The corresponding inequalities describe . Indeed, by separation, every point outside violates a valid inequality. Since that inequality is a nonnegative combination of the generator inequalities, the point must violate at least one of them.
Let , where is one of these defining inequalities and is positive somewhere on . Validity on implies for every . Thus (12) implies . The coefficients of have bits, and for every . Since , it follows that . To bound the retained slacks, apply the same construction to . Its homogenized cone has variables, and the additional inequality has bits per coefficient. By (11), therefore has
For each , Lemma 1 shows that is attained at one of these point generators. Since has bits per coefficient, (14) implies . If and , take . Then and , so the bound on follows directly from the point-generator bound following (12).
Proof of Theorem 1. Suppose , and let , where is a defining inequality from Lemma 4 that is violated on . Since on and somewhere on , we have . The split has branches and . To enforce in one split round, it therefore suffices to reach a relaxation on which .
Let and . We claim that on for every . At , this follows from the definition of . Suppose the claim holds at . Apply Lemma 3 with and . Then on . The number is the same at each application: the retained rows and their slack maxima in (5) are determined by and , and in (6) depends only on . This proves the claim. For , we have . Thus on , and the split enforces in round .
We now bound in terms of the input length, uniformly over the defining inequalities of . Lemma 4 implies , so . To bound , recall from (5) that . There are at most terms in the sum, each by Lemma 4, so . By (2) and (6), . Thus . The dense input records all matrix entries, so . Since , we have . It follows that each halving uses rounds and that . The constants are uniform over the defining rows. Hence there is an integer such that every row holds on . Indeed, rows valid on remain valid throughout, and a row derived at round holds on . Since these inequalities define , we have . Conversely, every split cut preserves all integer points of and therefore their convex hull . Thus .
Suppose and . Since contains no integer point, the inequality with is valid at every integer point of . Apply Lemma 3 with and . After rounds, every point of must satisfy . Since , this closure is empty. Lemma 4 bounds by also in this case, so the same estimate applies. If , then before any round.
Encoding the individual cuts
For a single split closure, each facet admits a defining inequality of encoding length polynomial in the input size [3 p. 347] (see also [7 Theorem 5.5 and Lemma 5.9]). We show that one polynomial in the original input length bounds the size of both the cuts and their justifying splits throughout the rounds of Theorem 1. In the proof of Lemma 3, the coefficients of in (8) depend on and and can be irrational. The strict bounds in (9) and (10) allow us to round these coefficients: at , the cut value exceeds , while on either branch at nonnegative height it is at most . We will use these bounds to construct a rational inequality that still excludes and is valid on both branches of the same split. The precision used in this rounding must therefore be uniform over the points , defining rows, and rounds.
Proposition 1. There is a polynomial such that rounds suffice to reach when each round imposes all rational cuts that are valid on both branches of a split in the current relaxation and for which the cut and its justifying split each have encoding length at most .
Proof. Let be a point in the current relaxation with that violates (7) at index , so that
We first bound the encoding length of the normal of the split chosen at . By (2),
Since , we have . For the th coordinate vector , Cauchy–Schwarz implies
Let be the largest absolute entry among the retained row normals and . The column has one entry for each and one entry , from the height term, for a total of entries. Each . Each halving starts with , so . Thus every entry has absolute value at most , and
Since , it follows that . Each has bits by the input bound, and each has bits by Lemma 4. Hence . As , each integer requires bits, and the coordinates of together require bits.
It remains to bound the split offset . Although can be unbounded, is constant along each recession direction of . Indeed, for every , the proof of Lemma 1 establishes for all and . Hence and . If denotes the set of point generators in (14), then . Since ,
Each coordinate of has bits, and each coordinate of has bits by (14). Since , the offset requires bits as well.
We next round the coefficients of . Rounding the coefficient of by changes the cut value by , for which there need not be a uniform bound on . Figure 5 illustrates how rounding in the original coordinates can exclude an integer point. The slacks in (4), however, satisfy and whenever and . We therefore express in these variables. For each slack , its contribution to the tangent is . Summing over the slacks and substituting into (8), we obtain

Figure 5. Rounding the same split cut to the nearest quarter. In coordinates , , the strip is and the original cut is (dashed boundary). Shading shows what each rounded cut retains. On the left, rounding in the original coordinates gives , which loses the integer point and retains . On the right, with , the cut is . Rounding gives , retaining the entire branch and excluding .
Round the constant and each coefficient of and in (16) to a nearest multiple of . Let denote the rounded value minus the original value for the constant, the coefficient of , and the coefficient of , respectively. Consecutive multiples of are apart, so each rounding error has absolute value at most . The weaker bound will suffice. For the resulting affine function , subtracting (16) gives
If and , then , so for each . Also, , since . By the triangle inequality,
We choose so that the error in (17) is at most . This preserves the strict signs in (9) and (10): a value greater than remains greater than , and a value at most remains at most . The required inequality is
or equivalently . Taking the base-two logarithm and rounding up, we may therefore choose
We now verify that is valid on both branches of and excludes . By (9) and (17), . By (10) and (17), at every branch point of nonnegative height in the current relaxation. The same bound holds on , since throughout that section. Now suppose a branch point with satisfies . Since , the segment meets at some point . The affine function is positive at both endpoints, so , a contradiction. Thus the rounded inequality is a split cut for the current relaxation.
We first bound the number of bits in the rounded coefficients of (16). By Lemma 4, there is an absolute constant such that for every . Since , we have . Substituting this estimate and into the choice of following (17), we obtain
We also need to bound the magnitude of each coefficient before rounding. Since , we have . The coefficient of in (16) has absolute value . The coefficient of has absolute value at most . For the constant term, (5) implies , so
where . Thus bounds the magnitude of every coefficient in (16). Rounding a coefficient to a nearest multiple means choosing an integer nearest to . Hence
Since , , and , each such integer requires bits.
It remains to express the rounded cut in the original variables. Denote its integer numerators by , so that
At halving , we have . Substituting and , we obtain
Every quantity on the right has integer coefficients. The factors and each require bits, since Lemma 4 bounds by and . The input coefficients require bits per entry, and require bits per entry by Lemma 4. Each product in the display requires bits. Each coefficient is a sum of such products, so it also requires bits. Since , the inequality defines the same halfspace as . Its integer coefficients therefore require bits in total.
Choose a polynomial that bounds the encoding lengths of the rounded cuts and their justifying splits for every defining row , and also for when . By Lemma 4, we may choose the same polynomial to cover the final cut and its split when . Let . For each , obtain by intersecting with every cut that is valid on both branches of a split in and for which the cut and the split each require at most bits. There are finitely many such pairs. Since these rounds impose only cuts of bounded length, may contain points outside . We therefore prove the halving bound directly on .
Fix and suppose a halving starts at , with throughout . We prove by induction on , for , that
At , this follows from (5). Suppose the bound holds at , and let satisfy and . Since , we have , so and the split in (2) applies. For every on either branch with , we also have , since . Equations (2), (6), and (8), together with the induction hypothesis on , imply
Thus (17) ensures that the rounded cut holds at these branch points.
Let lie on either branch with . By (9) and (17), . If , then is positive throughout because it is affine. Since , this segment contains a point with . But (3), (6), and (8) imply , so (17) implies , a contradiction. Thus the rounded inequality is valid on both branches of the chosen split in and excludes . Since both the cut and its split satisfy the length bound , this cut is imposed in forming , so . This proves the induction step.
Suppose satisfies . Then , so the induction bound at and the lower bound in (5) imply
where the strict inequality follows from . Thus throughout , and we can begin the next halving with upper bound . For each defining inequality violated on , the proof of Theorem 1 bounds the number of halvings by and the rounds per halving by .
Once , the split on enforces in one further round. Both this cut and its split satisfy the length bound . Taking the maximum of these round counts over the defining inequalities, we obtain for some . If and , one halving with and forces . If , then . Within each round, the finitely many eligible cuts can also be imposed successively: after any cut, both branches of each remaining split are subsets of their branches at the start of the round, so every remaining cut is still valid. □
AI use disclosure
During the preparation of this manuscript, the authors used OpenAI’s ChatGPT to find relevant literature outside of their knowledge, the development of induction arguments and checking the encoding bound, and the parts of the exposition including figures. The authors have verified and take full responsibility for the manuscript including the results, their proofs, and references.
Department of Industrial Engineering and Operations Research, Indian Institute of Technology Bombay, Mumbai 400076, India
Email address: [email protected]
Department of Industrial Engineering and Operations Research, Indian Institute of Technology Bombay, Mumbai 400076, India
Email address: [email protected]
References
- [1]Egon Balas, Disjunctive programming: properties of the convex hull of feasible points, Discrete Applied Mathematics 89 (1998), 3–44.DOI
- [2]Wojciech Banaszczyk, New bounds in some transference theorems in the geometry of numbers, Mathematische Annalen 296 (1993), 625–635.
- [3]Amitabh Basu, Michele Conforti, Marco Di Summa, and Hongyi Jiang, Split cuts in the plane, SIAM Journal on Optimization 31 (2021), 331–347.arxiv.org/abs/2003.05022
- [4]———, Complexity of branch-and-bound and cutting planes in mixed-integer optimization, Mathematical Programming 198 (2023), no. 1, 787–810.
- [5]Avinash Bhardwaj and Vishnu Narayanan, Split cuts in fixed integer dimensions, arXiv:2611.02169v2, 2026.arxiv.org/abs/2611.02169
- [6]Stephen Boyd and Lieven Vandenberghe, Convex optimization, Cambridge University Press, 2004.
- [7]Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli, Integer programming, Graduate Texts in Mathematics, vol. 271, Springer, 2014.
- [8]Michele Conforti, Alberto Del Pia, Marco Di Summa, and Yuri Faenza, Reverse split rank, Mathematical Programming 154 (2015), 273–303.
- [9]Michele Conforti, Alberto Del Pia, Marco Di Summa, Yuri Faenza, and Roland Grappe, Reverse Chvátal–Gomory rank, SIAM Journal on Discrete Mathematics 29 (2015), 166–181.
- [10]W. Cook, C. K. R. Coullard, and G. Turán, On the complexity of cutting-plane proofs, Discrete Applied Mathematics 18 (1987), 25–38.DOI
- [11]William Cook, Ravi Kannan, and Alexander Schrijver, Chvátal closures for mixed integer programming problems, Mathematical Programming 47 (1990), 155–174.DOI
- [12]Gérard Cornuéjols and Yanjun Li, On the rank of mixed 0,1 polyhedra, Mathematical Programming 91 (2002), 391–397.
- [13]Sanjeeb Dash, On the complexity of cutting-plane proofs using split cuts, Operations Research Letters 38 (2010), no. 2, 109–114.
- [14]Sanjeeb Dash and Yatharth Dubey, On polytopes with linear rank with respect to generalizations of the split closure, Discrete Optimization 51 (2024), 100821.
- [15]Johan Håstad, Dual vectors and lower bounds for the nearest lattice point problem, Combinatorica 8 (1988), 75–81.DOI
- [16]Alexander Schrijver, On cutting planes, Annals of Discrete Mathematics 9 (1980), 291–296.
- [17]———, Theory of linear and integer programming, John Wiley & Sons, 1986.

