betaFeedback

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 LL, then O((L+1)9)O((L+1)^9) split rounds suffice to reach the integer hull in arbitrary dimension.

Introduction

Let P={y∈Rn:aiTy≤bi, 1≤i≤m}P = \{y \in\mathbb{R}^n : a_i^{\mathsf{T}}y \le b_i,\ 1 \le i \le m\} be a rational polyhedron with integer hull PI=conv⁡(P∩Zn)P_I = \operatorname{conv}(P \cap\mathbb{Z}^n). Throughout, we assume without loss of generality that the defining inequalities of PP and PIP_I and the target inequality g≤0g \le0 have integer coefficients. A split (π,k)(\pi,k), where π∈Zn∖{0}\pi\in\mathbb{Z}^n \setminus\{0\} and k∈Zk \in\mathbb{Z}, has two branches, πTx≤k\pi^{\mathsf{T}}x \le k and πTx≥k+1\pi^{\mathsf{T}}x \ge k + 1. Every integer point satisfies one of them. An inequality valid on both branches in PP is a split cut for PP. One split round imposes all split cuts for the current relaxation. Starting from SC⁡0(P)=P\operatorname{SC}^0(P) = P, write SC⁡j(P)\operatorname{SC}^j(P) for the relaxation after jj rounds. The split rank of PP is the least integer j≥0j \ge0 such that SC⁡j(P)=PI\operatorname{SC}^j(P) = P_I. Schrijver proved that finitely many Chvátal–Gomory rounds suffice to reach PIP_I [16 Theorem 2]. Since every Chvátal–Gomory cut is a split cut, the split rank is finite. When PI=∅P_I = \varnothing, Cook, Coullard, and Turán [10 Theorem 1] proved that a number of Chvátal cuts depending only on the dimension suffices to reduce PP 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 TT be the triangle with vertices (0,0,0)(0, 0, 0), (2,0,0)(2, 0, 0), and (0,2,0)(0, 2, 0). For a positive integer HH, let THT_H be the tetrahedron obtained by adjoining the apex (1/2,1/2,H)(1/2, 1/2, H). Every point of THT_H at positive height satisfies x1>0x_1 > 0, x2>0x_2 > 0, and x1+x2<2x_1 + x_2 < 2. No integer pair satisfies these inequalities. Since the vertices of TT are integral, TT is the integer hull of THT_H. Conforti et al. showed that deriving x3≤0x_3 \le0 on THT_H requires Ω(log⁡H)\Omega(\log H) split rounds [9 Lemma 19]. The four inequalities defining THT_H take O(log⁡(H+1))O(\log(H + 1)) 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 P⊂RnP \subset\mathbb{R}^n be a rational pure-integer polyhedron given by a system of linear inequalities of dense binary encoding length LL. The split rank of PP is O((L+1)9)O((L + 1)^9).

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 [0,1]n[0,1]^n, taking the convex hull over the two branches of each coordinate split (ei,0)(e_i, 0) in succession gives the integer hull in at most

Key words and phrases. Split rank, integer hull, split cuts, cutting planes. nn rounds [1]. This bound is tight [12]. Even a polytope in the cube defined by O(n)O(n) inequalities can have empty integer hull and split rank Ω(n)\Omega(n) [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 LL.

Idea of the proof

For the tetrahedron THT_H, deriving x3≤0x_3 \le0 suffices to reach the integer hull. More generally, suppose PI≠∅P_I \ne\emptyset, and let g(x)=cTx+c0≤0g(x) = c^\mathsf{T}x + c_0 \le0 be a defining inequality of PIP_I that is violated somewhere on PP. We call g(x)g(x) the height of xx. Since PI≠∅P_I \ne\emptyset, PP and PIP_I have the same recession cone [17]. Validity of g≤0g \le0 on PIP_I therefore gives cTr≤0c^\mathsf{T}r \le0 for every r∈rec⁡(P)r \in\operatorname{rec}(P). Hence gg is bounded above on PP.

Figure 1. The convex function F(u,v)=v+(u−12)2F(u,v)=v+(u-\frac{1}{2})^2 is at most one at the vertices, hence throughout the polygon. Its tangent at x=(12,1)x=(\frac{1}{2},1) is T(u,v)=vT(u,v)=v. On both branches of (e1,0)(e_1,0), F−T=14F-T=\frac{1}{4}, so the raised tangent T+18≤1T+\frac{1}{8}\le1 cuts off the cap v>78v>\frac{7}{8} containing xx. The midpoint pp survives every cut from this split because it lies between the two marked branch points.

Let H=⌈max⁡x∈Pg(x)⌉H=\lceil\max_{x\in P}g(x)\rceil. We show that polynomially many split rounds suffice to halve the upper bound on gg. After 1+⌊log⁡2H⌋1+\lfloor\log_2 H\rfloor halvings, g(x)<1g(x)<1 for every xx in the current relaxation, so the branch g≥1g\ge1 contains no point of that relaxation. Thus the split (c,−c0)(c,-c_0) gives g≤0g\le0 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 PIP_I. Thus all these inequalities hold after the same polynomial number of rounds.

To see how one halving works, consider a bounded PP. Fix a point xx of height greater than H/4H/4. Around xx, we construct an ellipsoid small enough that every point in it still has positive height and satisfies aiTy<bi+1a_i^\mathsf{T}y<b_i+1 for every defining inequality aiTy≤bia_i^\mathsf{T}y\le b_i of PP. An integer point in the ellipsoid would therefore satisfy every defining inequality of PP and violate g≤0g\le0. Thus the ellipsoid contains no integer point. Banaszczyk’s theorem [2] then gives a split whose two branches stay a positive distance from xx, 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 xx agrees with the function at xx. 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 xx whenever it violates the bound for the next round. Figure 1 illustrates this step. At heights at least H/2H/2, 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 H/2H/2. Figure 2 shows how repeating this halving gives the rank bound.

Proof flowchart for Theorem 1

Figure 2. Proof of Theorem 1 for PI≠∅P_I \ne\varnothing. 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 PP with PI=∅P_I = \varnothing, one halving with g≡1g \equiv1 and H=1H = 1 suffices.

Halving the maximum violation

Let g(y)=cTy+c0g(y) = c^{\mathsf T}y + c_0 be bounded above on PP, with g≤0g \le0 on PIP_I. Suppose the current relaxation QQ satisfies PI⊆Q⊆PP_I \subseteq Q \subseteq P and g≤Hg \le H on QQ, where H>0H > 0. We seek to derive g≤H/2g \le H/2 by split cuts. If this bound already holds on QQ, no further rounds are needed. Otherwise, K=P∩{g≥0}K = P \cap\{g \ge0\} is nonempty. For each defining inequality aiTy≤bia_i^{\mathsf T}y \le b_i of PP, let si(y)=bi+1−aiTys_i(y) = b_i + 1 - a_i^{\mathsf T}y be its shifted slack. Then si≥1s_i \ge1 on PP, so log⁡si\log s_i is defined even where the inequality is tight. For z∈Znz \in\mathbb{Z}^n, si(z)s_i(z) is an integer, so si(z)>0s_i(z) > 0 is equivalent to aiTz≤bia_i^{\mathsf T}z \le b_i.

Distance to the split branches

To bound the variation of log⁡si\log s_i on KK, we also need an upper bound on sis_i. When PP is bounded, every shifted slack has a finite maximum on KK. For an unbounded example, take P=[0,12]×[0,∞)P = [0,\frac{1}{2}] \times[0,\infty) and g(y)=y1g(y) = y_1. Here K=PK = P, and the shifted slack 1+y21 + y_2 of the row y2≥0y_2 \ge0 is unbounded. We can omit this row because 0≤y1≤120 \le y_1 \le\frac{1}{2} already forces y1=0y_1 = 0 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 KK and whose inequalities exclude every integer point with g>0g > 0.

Lemma 1. There is a set J⊂{1,…,m}J \subset\{1,\ldots,m\} such that Bi=max⁡y∈Ksi(y)B_i = \max_{y \in K} s_i(y) is finite for each i∈Ji \in J, and every z∈Znz \in\mathbb{Z}^n satisfying aiTz≤bia_i^{\mathsf T}z \le b_i for all i∈Ji \in J has $g(z) \le 0.

Proof. Let R=rec⁡(K)R = \operatorname{rec}(K), the set of directions rr such that y+tr∈Ky + tr \in K for every y∈Ky \in K and t≥0t \ge0. Along each such direction, aiTr≤0a_i^{\mathsf T}r \le0 for every ii, since aiT(y+tr)≤bia_i^{\mathsf T}(y + tr) \le b_i for all t≥0t \ge0. Moreover, g(y+tr)=g(y)+tcTrg(y + tr) = g(y) + tc^{\mathsf T}r stays between 00 and max⁡Pg\max_P g, so cTr=0c^{\mathsf T}r = 0. Since RR is a rational polyhedral cone, it has a finite set EE of integer generators. Set r0=∑e∈Eer_0 = \sum_{e \in E} e, taking r0=0r_0 = 0 if R={0}R = \{0\}. Retain the rows whose slack stays constant along r0r_0, that is, J={i:aiTr0=0}J = \{i : a_i^{\mathsf T}r_0 = 0\}.

For each i∈Ji \in J, we have 0=aiTr0=∑e∈EaiTe0 = a_i^{\mathsf T}r_0 = \sum_{e \in E} a_i^{\mathsf T}e. Since aiTe≤0a_i^{\mathsf T}e \le0 for every e∈Ee \in E, it follows that aiTe=0a_i^{\mathsf T}e = 0 for every e∈Ee \in E. As EE generates RR, we have aiTr=0a_i^{\mathsf T}r = 0 for every r∈Rr \in R. By the Minkowski–Weyl theorem, K=conv⁡(V)+RK = \operatorname{conv}(V) + R for some finite nonempty set VV. Thus si(v+r)=si(v)s_i(v+r) = s_i(v) for v∈conv⁡(V)v \in\operatorname{conv}(V) and r∈Rr \in R. Since sis_i is affine, Bi=max⁡v∈Vsi(v)<∞B_i = \max_{v \in V} s_i(v) < \infty.

Let z∈Znz \in\mathbb{Z}^n satisfy aiTz≤bia_i^{\mathsf T}z \le b_i for every i∈Ji \in J. For i∈Ji \in J, we have aiTr0=0a_i^{\mathsf T}r_0 = 0, so aiT(z+tr0)=aiTz≤bia_i^{\mathsf T}(z + tr_0) = a_i^{\mathsf T}z \le b_i for every t≥0t \ge0. For i∉Ji \notin J, we have aiTr0<0a_i^{\mathsf T}r_0 < 0, so aiT(z+tr0)≤bia_i^{\mathsf T}(z + tr_0) \le b_i whenever

t≥aiTz−bi−aiTr0.t \ge\frac{a_i^{\mathsf T}z - b_i}{-a_i^{\mathsf T}r_0}.

Choose a nonnegative integer tt at least as large as each of these finitely many lower bounds. Then z+tr0z+tr_0 satisfies every defining inequality of PP. Since zz and r0r_0 are integral, z+tr0∈P∩Znz+tr_0\in P\cap\mathbb{Z}^n, where g≤0g\leq0. As cTr0=0c^{\mathsf{T}}r_0=0, we obtain g(z)=g(z+tr0)≤0g(z)=g(z+tr_0)\leq0.

Lemma 1 shows that the region where g>0g>0 and si>0s_i>0 for every i∈Ji\in J contains no integer point. To find a split whose two branches stay away from a point xx of positive height, we first bound how far xx can move while remaining in this region. Let h=H/4h=H/4 and consider x∈Qx\in Q with g(x)≥hg(x)\geq h. The matrix DxD_x has rows aiT/si(x)a_i^{\mathsf{T}}/s_i(x) for i∈Ji\in J and last row cT/(g(x)+h)c^{\mathsf{T}}/(g(x)+h). For y∈Rny\in\mathbb{R}^n,

∥Dx(y−x)∥22=∑i∈J(si(y)−si(x)si(x))2+(g(y)−g(x)g(x)+h)2.(1)\lVert D_x(y-x)\rVert_2^2=\sum_{i\in J}\left(\frac{s_i(y)-s_i(x)}{s_i(x)}\right)^2+\left(\frac{g(y)-g(x)}{g(x)+h}\right)^2. \tag*{(1)}

If ∥Dx(y−x)∥2<1/2\lVert D_x(y-x)\rVert_2<1/2, each ratio in (1) has absolute value less than 1/21/2. Hence si(y)>si(x)/2>0s_i(y)>s_i(x)/2>0 for every i∈Ji\in J, and g(y)>(g(x)−h)/2≥0g(y)>(g(x)-h)/2\geq0.

We now consider the images of the integer points in W=DxRnW=D_x\mathbb{R}^n. For z∈Znz\in\mathbb{Z}^n, each aiTza_i^{\mathsf{T}}z and cTzc^{\mathsf{T}}z is an integer. Thus the coordinate of DxzD_xz corresponding to row i∈Ji\in J is an integer multiple of 1/si(x)1/s_i(x), and its last coordinate is an integer multiple of 1/(g(x)+h)1/(g(x)+h). Two distinct points of Λ=DxZn\Lambda=D_x\mathbb{Z}^n differ in at least one coordinate. Their distance is therefore at least the smallest of these positive spacings. Hence Λ\Lambda is discrete. It is the additive group generated by the columns of DxD_x, since DxzD_xz is their linear combination with coefficients z1,…,znz_1,\ldots,z_n. Those same columns span WW over R\mathbb{R}, so Λ\Lambda is a lattice spanning WW.

Suppose a point of Λ\Lambda were at distance less than 1/21/2 from DxxD_xx. That point has the form DxzD_xz for some z∈Znz\in\mathbb{Z}^n, so ∥Dx(z−x)∥2<1/2\lVert D_x(z-x)\rVert_2<1/2. By (1), si(z)>0s_i(z)>0 for every i∈Ji\in J and g(z)>0g(z)>0. Since zz is integral, si(z)>0s_i(z)>0 implies aiTz≤bia_i^{\mathsf{T}}z\leq b_i. Thus zz satisfies every inequality indexed by JJ, and Lemma 1 implies g(z)≤0g(z)\leq0, a contradiction. Hence dist⁡(Dxx,Λ)≥1/2\operatorname{dist}(D_xx,\Lambda)\geq1/2.

The bound dist⁡(Dxx,Λ)≥1/2\operatorname{dist}(D_xx,\Lambda)\geq1/2 measures the distance to the nearest lattice point. To construct a split, we need a direction in which DxxD_xx lies between two consecutive parallel hyperplanes and stays a positive distance from both. We choose the direction from the dual lattice

Λ∗={u∈W:⟨u,z⟩∈Z for every z∈Λ}.\Lambda^*=\{u\in W:\langle u,z\rangle\in\mathbb{Z}\text{ for every }z\in\Lambda\}.

For 0≠u∈Λ∗0\neq u\in\Lambda^*, every point of Λ\Lambda lies on one of the hyperplanes ⟨u,w⟩=k\langle u,w\rangle=k, k∈Zk\in\mathbb{Z}. The distance from p∈Wp\in W to the hyperplane indexed by kk is ∣⟨u,p⟩−k∣/∥u∥2\lvert\langle u,p\rangle-k\rvert/\lVert u\rVert_2. Minimizing over k∈Zk\in\mathbb{Z} yields the distance to the nearest hyperplane. For d=dim⁡Wd=\dim W, Håstad [15] showed that one can choose u∈Λ∗∖{0}u\in\Lambda^*\setminus\{0\} so that the distance from pp to the nearest of these hyperplanes is at least dist⁡(p,Λ)/(6d2+1)\operatorname{dist}(p,\Lambda)/(6d^2+1). Banaszczyk [2, Theorem 2.3] improved the dependence of the denominator on dd from quadratic to linear. We use the following consequence of his theorem.

Lemma 2. Let Λ\Lambda be a lattice spanning a Euclidean space WW of dimension d≥1d\geq1. For every p∈W∖Λp\in W\setminus\Lambda, there is a nonzero u∈Λ∗u\in\Lambda^* such that

dist⁡(⟨u,p⟩,Z)∥u∥2≥dist⁡(p,Λ)6d.\frac{\operatorname{dist}(\langle u,p\rangle,\mathbb{Z})}{\lVert u\rVert_2}\geq\frac{\operatorname{dist}(p,\Lambda)}{6d}.

Proof. Suppose d≥2d\geq2. By Banaszczyk [2, Theorem 2.3], there is a vector u∈Λ∗u\in\Lambda^* satisfying

∥u∥2dist⁡(p,Λ)≤d,cos⁡(2π⟨u,p⟩)≤110.\lVert u\rVert_2\operatorname{dist}(p,\Lambda)\leq d,\qquad\cos(2\pi\langle u,p\rangle)\leq\frac{1}{10}.

Let kk be an integer nearest to ⟨u,p⟩\langle u,p\rangle. If ∣⟨u,p⟩−k∣≤1/6\lvert\langle u,p\rangle-k\rvert\leq1/6, then cos⁡(2π⟨u,p⟩)=cos⁡(2π(⟨u,p⟩−k))≥1/2\cos(2\pi\langle u,p\rangle)=\cos(2\pi(\langle u,p\rangle-k))\geq1/2, contrary to the second inequality. Thus dist⁡(⟨u,p⟩,Z)>1/6\operatorname{dist}(\langle u,p\rangle,\mathbb{Z})>1/6, which also implies u≠0u\neq0. The first inequality implies 1/∥u∥2≥dist⁡(p,Λ)/d1/\lVert u\rVert_2\geq\operatorname{dist}(p,\Lambda)/d. Multiplying these bounds proves the claim.

For d=1d=1, choose a unit coordinate in which Λ=bZ\Lambda=b\mathbb{Z}, with b>0b>0. Then u=1/bu=1/b belongs to Λ∗\Lambda^*, and

dist⁡(⟨u,p⟩,Z)∥u∥2=bmin⁡k∈Z∣p/b−k∣=min⁡k∈Z∣p−bk∣=dist⁡(p,Λ).\frac{\operatorname{dist}(\langle u,p\rangle,\mathbb{Z})}{\lVert u\rVert_2} =b\min_{k\in\mathbb{Z}}\lvert p/b-k\rvert =\min_{k\in\mathbb{Z}}\lvert p-bk\rvert =\operatorname{dist}(p,\Lambda).

Lemma 2 determines a split in the original variables. Take p=Dxxp = D_{x}x and let u∈Λ∗u \in\Lambda^{*} satisfy the lemma. The vector π=DxTu\pi= D_{x}^{\mathsf{T}}u is integral because each of its entries is the inner product of uu with a column of DxD_{x}, and each column belongs to Λ\Lambda. Since dist⁡(p,Λ)≥1/2\operatorname{dist}(p,\Lambda) \ge1/2, Lemma 2 implies that πTx=⟨u,p⟩\pi^{\mathsf{T}}x = \langle u,p\rangle is not an integer. In particular, π≠0\pi\ne0. Let k=⌊πTx⌋k = \lfloor\pi^{\mathsf{T}}x\rfloor. For yy on either branch of (π,k)(\pi,k), the interval between πTx\pi^{\mathsf{T}}x and πTy\pi^{\mathsf{T}}y contains kk or k+1k+1. Thus ∣πT(y−x)∣≥dist⁡(πTx,Z)\lvert\pi^{\mathsf{T}}(y-x)\rvert\ge\operatorname{dist}(\pi^{\mathsf{T}}x,\mathbb{Z}). By Cauchy–Schwarz and Lemma 2,

∥Dx(y−x)∥2≥∣πT(y−x)∣∥u∥2≥dist⁡(πTx,Z)∥u∥2≥112n=:η.(2)\lVert D_{x}(y-x)\rVert_{2} \ge\frac{\lvert\pi^{\mathsf{T}}(y-x)\rvert}{\lVert u\rVert_{2}} \ge\frac{\operatorname{dist}(\pi^{\mathsf{T}}x,\mathbb{Z})}{\lVert u\rVert_{2}} \ge\frac{1}{12n} =: \eta. \tag*{(2)}

where the last inequality uses dist⁡(p,Λ)≥1/2\operatorname{dist}(p,\Lambda) \ge1/2 and dim⁡W≤n\dim W \le n. Figure 3 illustrates the distances from pp to the lattice and to the nearer split branch.

Distances from $p$ to the lattice and to the nearer split branch

Figure 3. From p=(14,12)p = \left(\frac{1}{4}, \frac{1}{2}\right), the nearest point of Z2\mathbb{Z}^{2} is at distance 5/4\sqrt{5}/4 (dotted), and the nearer branch of (e1,0)(e_{1},0) is at distance 1/41/4 (solid). The ball of radius 1/21/2 about pp contains no lattice point but meets the left branch.

To prove that a cut holds at a branch point yy with g(y)<0g(y) < 0, we will use the point where the segment [x,y][x,y] crosses g=0g=0. This point can lie between the branches, where (2) does not apply. On the entire section g=0g=0, however, the height term in (1) already suffices. For every ww with g(w)=0g(w)=0,

∥Dx(w−x)∥2≥∣g(w)−g(x)∣g(x)+h=g(x)g(x)+h≥12,(3)\lVert D_{x}(w-x)\rVert_{2} \ge\frac{\lvert g(w)-g(x)\rvert}{g(x)+h} = \frac{g(x)}{g(x)+h} \ge\frac{1}{2}, \tag*{(3)}

since g(x)≥hg(x) \ge h.

The halving bound

We use the distance estimates (2) and (3) to bound the gap between a convex function and its affine tangent at xx. 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 g=0g=0. For y∈Py \in P with 0≤g(y)≤H0 \le g(y) \le H, let

t(y)=g(y)+hh,F(y)=−∑i∈Jlog⁡si(y)−log⁡t(y),(4)t(y) = \frac{g(y)+h}{h}, \qquad F(y) = -\sum_{i\in J}\log s_i(y)-\log t(y), \tag*{(4)}

where log⁡\log is the natural logarithm. Since h=H/4h=H/4, we have 1≤t(y)≤51 \le t(y) \le5. Also, y∈Ky \in K, so 1≤si(y)≤Bi1 \le s_i(y) \le B_i for every i∈Ji \in J. Consequently,

−Δ≤F(y)≤0,Δ=log⁡5+∑i∈Jlog⁡Bi.(5)-\Delta\le F(y) \le0, \qquad\Delta= \log5 + \sum_{i\in J}\log B_i. \tag*{(5)}

The same Δ\Delta applies at every halving because KK, JJ, and the BiB_i depend only on PP and gg.

Let Tx(y)=F(x)+∇F(x)T(y−x)T_x(y)=F(x)+\nabla F(x)^{\mathsf{T}}(y-x) be the affine tangent to FF at xx. For each ss among the shifted slacks (si)i∈J(s_i)_{i\in J} and tt, let vs=(s(y)−s(x))/s(x)v_s=(s(y)-s(x))/s(x). Since s(y)=s(x)(1+vs)s(y)=s(x)(1+v_s), the change in −log⁡s-\log s from xx to yy is −log⁡(1+vs)-\log(1+v_s). The corresponding change in its tangent is −vs-v_s, since the derivative of −log⁡-\log at s(x)s(x) is −1/s(x)-1/s(x). Summing over ss, we obtain

F(y)−Tx(y)=∑s(vs−log⁡(1+vs)).F(y)-T_x(y)=\sum_s\left(v_s-\log(1+v_s)\right).

These are the same relative changes that appear in (1): in particular, vt=(g(y)−g(x))/(g(x)+h)v_t = (g(y) - g(x))/(g(x) + h). Thus ∑svs2=∥Dx(y−x)∥22\sum_s v_s^2 = \lVert D_x(y-x)\rVert_2^2, the quadratic form of the Hessian of FF at xx evaluated on y−xy-x [6 Section 11.2]. To bound the tangent gap from below, it remains to compare v−log⁡(1+v)v-\log(1+v) with v2v^2.

Let ψ(v)=v−log⁡(1+v)\psi(v) = v - \log(1+v) for v>−1v > -1. Since ψ(0)=ψ′(0)=0\psi(0) = \psi'(0) = 0 and ψ′′(v)=1/(1+v)2>0\psi''(v) = 1/(1+v)^2 > 0, the minimum of ψ\psi is zero. On (−1,1](-1,1], we have ψ′′(v)≥1/4\psi''(v) \ge1/4, so Taylor’s theorem at zero implies ψ(v)≥v2/8\psi(v) \ge v^2/8. For v>1v > 1, we have ψ′(v)=v/(1+v)>0\psi'(v) = v/(1+v) > 0, so ψ(v)≥ψ(1)=1−log⁡2>1/8\psi(v) \ge\psi(1) = 1-\log2 > 1/8.

Let yy lie on either branch of the split (π,k)(\pi,k), with 0≤g(y)≤H0 \le g(y) \le H. By (2), ∥Dx(y−x)∥2≥η\lVert D_x(y-x)\rVert_2 \ge\eta. Squaring and using (1), we obtain

∑svs2=∥Dx(y−x)∥22≥η2.\sum_s v_s^2 = \lVert D_x(y-x)\rVert_2^2 \ge\eta^2.

If every vs≤1v_s \le1, then ψ(vs)≥vs2/8\psi(v_s) \ge v_s^2/8 for each ss. Summing these inequalities yields

F(y)−Tx(y)=∑sψ(vs)≥18∑svs2≥η28.F(y)-T_x(y) = \sum_s \psi(v_s) \ge\frac{1}{8}\sum_s v_s^2 \ge\frac{\eta^2}{8}.

If some vs>1v_s > 1, then ψ(vs)>1/8\psi(v_s) > 1/8. All other terms are nonnegative, so F(y)−Tx(y)>1/8≥η2/8F(y)-T_x(y) > 1/8 \ge\eta^2/8, since η=1/(12n)≤1\eta= 1/(12n) \le1. In both cases the only property of the split branch used was the distance bound in (2). Thus, for every y∈Py \in P with 0≤g(y)≤H0 \le g(y) \le H,

∥Dx(y−x)∥2≥η⟹F(y)−Tx(y)≥4γ,γ=η232.(6)\lVert D_x(y-x)\rVert_2 \ge\eta\quad\Longrightarrow\quad F(y)-T_x(y) \ge4\gamma,\qquad\gamma= \frac{\eta^2}{32}. \tag*{(6)}

In particular, (6) also applies on the entire section g=0g=0, since (3) bounds the distance there by at least 1/21/2. We use this gap in successive split rounds to lower the upper bound on FF at points with g≥H/2g \ge H/2. Once that upper bound falls below −Δ-\Delta, (5) excludes every such point.

Lemma 3. If g≤Hg \le H on QQ, then g≤H/2g \le H/2 on SC⁡b(Q)\operatorname{SC}^{b}(Q) for b=1+⌊4Δ/γ⌋b = 1 + \lfloor4\Delta/\gamma\rfloor.

Proof. Let Qj=SC⁡j(Q)Q_j = \operatorname{SC}^{j}(Q). We seek an upper bound on FF that decreases with each round at points of height at least H/2H/2. The split in (2) is available when g≥hg \ge h, where h=H/4h = H/4. To account for this threshold, let ϕ(y)=(g(y)−h)/H\phi(y) = (g(y)-h)/H. Then ϕ(y)≤0\phi(y) \le0 when g(y)≤hg(y) \le h, and ϕ(y)≥1/4\phi(y) \ge1/4 when g(y)≥H/2g(y) \ge H/2. We prove by induction on jj that

F(y)+jγϕ(y)≤0for every y∈Qj with g(y)≥0.(7)F(y) + j\gamma\phi(y) \le0 \qquad\text{for every } y \in Q_j \text{ with } g(y) \ge0. \tag*{(7)}

For j=0j=0, this is the upper bound F(y)≤0F(y) \le0 in (5). When 0≤g(y)≤h0 \le g(y) \le h, both terms on the left of (7) are nonpositive for every jj. When g(y)≥H/2g(y) \ge H/2, (7) requires F(y)≤−jγ/4F(y) \le-j\gamma/4.

Assume (7) holds on QjQ_j, and let x∈Qjx \in Q_j with g(x)≥0g(x) \ge0 satisfy

F(x)+(j+1)γϕ(x)>0.F(x) + (j+1)\gamma\phi(x) > 0.

Since F(x)≤0F(x) \le0 by (5), we must have ϕ(x)>0\phi(x) > 0. Thus g(x)>hg(x) > h by the definition of ϕ\phi, and the split (π,k)(\pi,k) in (2) applies at xx. Since ϕ\phi is affine, the tangent at xx to F+jγϕF+j\gamma\phi is Tx+jγϕT_x+j\gamma\phi.

Let y∈Qjy \in Q_j lie on either branch of (π,k)(\pi,k), with g(y)≥0g(y) \ge0. Since Qj⊆QQ_j \subseteq Q, we have g(y)≤Hg(y) \le H. By (2), ∥Dx(y−x)∥2≥η\lVert D_x(y-x)\rVert_2 \ge\eta, so (6) implies F(y)−Tx(y)≥4γF(y)-T_x(y) \ge4\gamma. Adding jγϕ(y)j\gamma\phi(y) to both sides of Tx(y)≤F(y)−4γT_x(y) \le F(y)-4\gamma yields

Tx(y)+jγϕ(y)≤F(y)+jγϕ(y)−4γ≤−4γ,T_x(y) + j\gamma\phi(y) \le F(y) + j\gamma\phi(y) - 4\gamma\le-4\gamma,

where the last inequality follows from the induction hypothesis (7). Thus we can raise the tangent by 2γ2\gamma and still have ℓx(y)≤−2γ\ell_x(y) \le-2\gamma on both branches at nonnegative height, where

ℓx(y)=Tx(y)+jγϕ(y)+2γ.(8)\ell_x(y) = T_x(y) + j\gamma\phi(y) + 2\gamma. \tag*{(8)}

The coefficients of ℓx\ell_x 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 xx.

At xx, we have Tx(x)=F(x)T_x(x)=F(x) and ϕ(x)≤3/4\phi(x)\le3/4, since g(x)≤Hg(x)\le H. Hence

ℓx(x)=F(x)+(j+1)γϕ(x)+(2−ϕ(x))γ>γ.(9)\ell_x(x)=F(x)+(j+1)\gamma\phi(x)+(2-\phi(x))\gamma>\gamma. \tag*{(9)}

Thus xx violates ℓx≤0\ell_x\le0, whereas every y∈Qjy\in Q_j on either branch with g(y)≥0g(y)\ge0 satisfies

ℓx(y)≤F(y)+jγϕ(y)−2γ≤−2γ.(10)\ell_x(y)\le F(y)+j\gamma\phi(y)-2\gamma\le-2\gamma. \tag*{(10)}

The bound ℓx(w)≤−2γ\ell_x(w)\le-2\gamma also holds for every w∈Pw\in P with g(w)=0g(w)=0, including points between the two branches. Indeed, (3) implies ∥Dx(w−x)∥2≥1/2≥η\lVert D_x(w-x)\rVert_2\ge1/2\ge\eta, so Tx(w)≤F(w)−4γT_x(w)\le F(w)-4\gamma by (6). Since F(w)≤0F(w)\le0 by (5) and ϕ(w)=−1/4\phi(w)=-1/4, equation (8) implies

ℓx(w)≤F(w)−4γ−jγ4+2γ≤−2γ.\ell_x(w)\le F(w)-4\gamma-\frac{j\gamma}{4}+2\gamma\le-2\gamma.

Now let y∈Qjy\in Q_j lie on either branch with g(y)<0g(y)<0. Since g(x)>h>0g(x)>h>0, the segment [x,y][x,y] contains a point ww with g(w)=0g(w)=0. If ℓx(y)>0\ell_x(y)>0, then ℓx(x)>0\ell_x(x)>0 by (9), and affineness implies ℓx(w)>0\ell_x(w)>0, contradicting ℓx(w)≤−2γ\ell_x(w)\le-2\gamma. Thus ℓx(y)≤0\ell_x(y)\le0 on both branches at negative height as well. Together with (10), this proves that ℓx≤0\ell_x\le0 is a split cut for QjQ_j. For every x∈Qjx\in Q_j with g(x)≥0g(x)\ge0 and

F(x)+(j+1)γϕ(x)>0,F(x)+(j+1)\gamma\phi(x)>0,

we have constructed a split cut for QjQ_j that excludes xx. Since Qj+1=SC⁡(Qj)Q_{j+1}=\operatorname{SC}(Q_j) satisfies every split cut for QjQ_j, every y∈Qj+1y\in Q_{j+1} with g(y)≥0g(y)\ge0 satisfies

F(y)+(j+1)γϕ(y)≤0.F(y)+(j+1)\gamma\phi(y)\le0.

This proves the induction step.

Suppose y∈Qjy\in Q_j satisfies g(y)≥H/2g(y)\ge H/2. Since h=H/4h=H/4, we have ϕ(y)=(g(y)−h)/H≥1/4\phi(y)=(g(y)-h)/H\ge1/4. The lower bound in (5) and the upper bound in (7) therefore imply

−Δ≤F(y)≤−jγϕ(y)≤−jγ4.-\Delta\le F(y)\le-j\gamma\phi(y)\le-\frac{j\gamma}{4}.

Such a point can exist only if j≤4Δ/γj\le4\Delta/\gamma. Since b=1+⌊4Δ/γ⌋>4Δ/γb=1+\lfloor4\Delta/\gamma\rfloor>4\Delta/\gamma, every y∈Qb=SC⁡b(Q)y\in Q_b=\operatorname{SC}^{b}(Q) satisfies g(y)<H/2g(y)<H/2, as illustrated in Figure 4.

Figure 4. In the normalized coordinates (g/H,F/Δ)(g/H,F/\Delta), the dashed line of slope −4-4 passes through (1/2,−1)(1/2,-1). When jγ/Δ>4j\gamma/\Delta>4, the upper bound in (7) is steeper, so the shaded region satisfying (5) and (7) lies entirely in g<H/2g<H/2.

The rank bound

Lemma 3 bounds the number of split rounds needed to halve an upper bound on gg. To prove Theorem 1 for PI≠∅P_I\ne\varnothing, we need two estimates for each defining inequality g≤0g\le0 of PIP_I that is violated on PP. The initial height H0=⌈max⁡Pg⌉H_0=\lceil\max_P g\rceil determines how many halvings are needed to reach g<1g<1. The quantity Δ\Delta in (5) determines how many rounds each halving takes. We bound both in terms of the input length LL. Let N=L+1N=L+1. The dense encoding counts every coefficient and right-hand side, including zeros, and each entry in the integer description of PP requires O(N)O(N) bits. If m=0m=0, then P=Rn=conv⁡(Zn)P=\mathbb{R}^n=\operatorname{conv}(\mathbb{Z}^n). If n=0n=0, then PP is either empty or consists of the unique point of R0\mathbb{R}^0, which is integral. In either case P=PIP=P_I, so the split rank is zero. We may therefore assume m,n≥1m,n\ge1. The dense encoding records nn coefficients and one right-hand side for each of the mm inequalities, so L≥m(n+1)L\ge m(n+1). In particular, m,n≤Nm,n\le N.

Lemma 4. Suppose PI≠∅P_I\ne\varnothing. Then PIP_I has a finite description by inequalities g≤0g\le0 with O(N3)O(N^3) bits per coefficient, including the constant term. For each inequality in this description that is violated on PP, the maximum of gg on PP is finite. With H0=⌈max⁡Pg⌉H_0=\lceil\max_P g\rceil and Bi=max⁡y∈Ksi(y)B_i=\max_{y\in K}s_i(y) for the rows i∈Ji\in J of Lemma 1, we have

log⁡2(1+H0)=O(N3),log⁡Bi=O(N4)(i∈J).\log_2(1+H_0)=O(N^3), \qquad\log B_i=O(N^4)\qquad(i\in J).

If P≠∅P\ne\varnothing and PI=∅P_I=\varnothing, the same bounds hold for g≡1g\equiv1 and $H_0=1.

Proof. We use a determinant bound three times. First, we bound the coordinates of the point and recession generators of PP. These bounds determine a box BB large enough that PI=conv⁡(P∩B∩Zn)+rec⁡(P)P_I=\operatorname{conv}(P\cap B\cap\mathbb{Z}^n)+\operatorname{rec}(P). Second, we use this description to express validity of an inequality g≤0g\le0 as a system of linear inequalities in the coefficients of gg. Applying the determinant bound to this system bounds the coefficients of a defining description of PIP_I. We then bound H0H_0 by evaluating each defining function gg on the point generators of PP. Third, we apply the determinant bound to K=P∩{g≥0}K=P\cap\{g\ge0\}. By Lemma 1, each retained slack sis_i is constant along every recession direction of KK, so its maximum BiB_i is attained at a point generator of KK.

Let C={w∈Rd:Aw≤0}C=\{w\in\mathbb{R}^d:Aw\le0\}, where AA is an integer matrix and ∣Aij∣≤2q\lvert A_{ij}\rvert\le2^q for some q≥1q\ge1. We show that CC has a finite set of integer generators, each of whose coordinates requires at most

O(d(q+log⁡(d+1))) bits.(11)O\bigl(d(q+\log(d+1))\bigr)\ \text{bits}. \tag*{(11)}

The cone CC may contain a line. To obtain cones generated by extreme rays, intersect CC with each coordinate orthant. In particular, for each σ∈{−1,1}d\sigma\in\{-1,1\}^d, let

Cσ={w∈C:σjwj≥0 for j=1,…,d}.C_\sigma=\{w\in C:\sigma_jw_j\ge0\text{ for }j=1,\ldots,d\}.

These cones cover CC, since every vector has a choice of coordinate signs. Each CσC_\sigma is pointed: if ww and −w-w both belong to CσC_\sigma, then σjwj=0\sigma_jw_j=0 for every jj, so w=0w=0. Let r≠0r\ne0 lie on an extreme ray of CσC_\sigma. Form MM from the rows AiA_i for which Air=0A_ir=0 and the rows σjejT\sigma_je_j^{\mathsf T} for which rj=0r_j=0. These are precisely the constraints defining CσC_\sigma that hold with equality at rr. Since Mr=0Mr=0 and r≠0r\ne0, we have rank⁡(M)≤d−1\operatorname{rank}(M)\le d-1. If the rank were smaller, the nullspace of MM would contain a vector vv linearly independent of rr. Then M(r±εv)=0M(r\pm\varepsilon v)=0, and for sufficiently small ε>0\varepsilon>0, all remaining inequalities would still hold because they are strict at rr. Thus rr would be the midpoint of two points of CσC_\sigma outside its ray, contradicting extremality. Hence rank⁡(M)=d−1\operatorname{rank}(M)=d-1.

For d≥2d\ge2, choose d−1d-1 linearly independent rows of MM and let BB be the matrix with these rows. Since Br=0Br=0 and BB has rank d−1d-1, its nullspace is the line spanned by rr. To find an integer vector on this line, let BjB_j be the square matrix obtained by deleting column jj of BB, and define

uj=(−1)j+1det⁡Bj,j=1,…,d.u_j=(-1)^{j+1}\det B_j,\qquad j=1,\ldots,d.

To verify Bu=0Bu=0, consider any row bTb^{\mathsf T} of BB. Placing bTb^{\mathsf T} above BB produces a square matrix with two identical rows, so its determinant is zero. Expanding along the first row yields ∑j=1dbj(−1)j+1det⁡Bj=bTu\sum_{j=1}^d b_j(-1)^{j+1}\det B_j=b^{\mathsf T}u. Thus bTu=0b^{\mathsf T}u=0 for every row of BB. Since BB has rank d−1d-1, some d−1d-1 columns are linearly independent, so at least one determinant det⁡Bj\det B_j is nonzero. Thus uu is a nonzero integer vector in span⁡(r)\operatorname{span}(r). Since r≠0r\ne0, either uu or −u-u generates the ray containing rr.

Each row of BB is either a row of AA or a coordinate row σjejT\sigma_je_j^{\mathsf T}, so every entry has absolute value at most 2q2^q. Each of the d−1d-1 rows of BjB_j therefore has Euclidean norm at most d 2q\sqrt{d}\,2^q. Hadamard’s inequality bounds the absolute determinant by the product of these row norms. Hence

∣uj∣≤(d 2q)d−1.\lvert u_j\rvert\le\bigl(\sqrt{d}\,2^q\bigr)^{d-1}.

The binary length of uju_j, including its sign, is consequently at most (d−1)(q+12log⁡2d)+O(1)(d-1)(q+\frac{1}{2}\log_2 d)+O(1), as required in (11). For d=1d=1, the positive and negative rays have generators 11 and −1-1, respectively, so (11) also holds.

Finally, each CσC_\sigma is a pointed polyhedral cone, so it is generated by its finitely many extreme rays. Every w∈Cw\in C belongs to some CσC_\sigma and is therefore a nonnegative combination of the generators chosen for that cone. Conversely, every chosen generator lies in CC, and CC contains all their nonnegative combinations. Taking the generators over the finitely many sign vectors σ\sigma therefore gives a finite generating set for CC satisfying (11).

By the Minkowski–Weyl theorem, P={y:Ay≤b}P=\{y:Ay\le b\} has finite sets of point generators VV and recession generators EE such that

P=conv⁡(V)+cone⁡(E),rec⁡(P)=cone⁡(E).(12)P=\operatorname{conv}(V)+\operatorname{cone}(E),\qquad\operatorname{rec}(P)=\operatorname{cone}(E). \tag*{(12)}

To bound their coordinates, apply (11) to the homogenized cone P^={(y,t):Ay≤tb, t≥0}\widehat{P}=\{(y,t):Ay\le tb,\ t\ge0\}. From its integer generators, take v/t∈Vv/t\in V for each (v,t)(v,t) with t>0t>0, and e∈Ee\in E for each (e,0)(e,0). The system defining P^\widehat{P} has n+1n+1 variables and O(N)O(N) bits per coefficient. Since n≤Nn\le N, (11) bounds each generator coordinate by O(N2)O(N^2) bits. As tt is a positive integer for each point generator, ∥v/t∥∞≤∥v∥∞\lVert v/t\rVert_\infty\le\lVert v\rVert_\infty. Thus every vector in V∪EV\cup E has infinity norm at most 2O(N2)2^{O(N^2)}.

Suppose PI≠∅P_I\ne\varnothing. Let B=1+max⁡v∈V∥v∥∞+nmax⁡e∈E∥e∥∞B=1+\max_{v\in V}\lVert v\rVert_\infty+n\max_{e\in E}\lVert e\rVert_\infty, taking the second maximum to be zero if E=∅E=\varnothing. For ZB=P∩Zn∩[−B,B]nZ_B=P\cap\mathbb{Z}^n\cap[-B,B]^n, we claim that

PI=conv⁡(ZB)+rec⁡(P).(13)P_I=\operatorname{conv}(Z_B)+\operatorname{rec}(P). \tag*{(13)}

Let y∈P∩Zny\in P\cap\mathbb{Z}^n. By (12) and conic Carathéodory [17 Corollary 7.1i], y=v+∑j=1kλjejy=v+\sum_{j=1}^{k}\lambda_j e_j for some v∈conv⁡(V)v\in\operatorname{conv}(V), ej∈Ee_j\in E, and λj≥0\lambda_j\ge0, with k≤nk\le n. The point

z=y−∑j=1k⌊λj⌋ej=v+∑j=1k(λj−⌊λj⌋)ejz=y-\sum_{j=1}^{k}\lfloor\lambda_j\rfloor e_j=v+\sum_{j=1}^{k}(\lambda_j-\lfloor\lambda_j\rfloor)e_j

is integral by the first equality and belongs to PP by the second. Each remaining coefficient is less than one, so ∥z∥∞<B\lVert z\rVert_\infty<B by the choice of BB. Thus z∈ZBz\in Z_B and y−z∈rec⁡(P)y-z\in\operatorname{rec}(P). Taking convex hulls proves the forward inclusion in (13).

Conversely, conv⁡(ZB)⊆PI\operatorname{conv}(Z_B)\subseteq P_I, and rec⁡(P)=rec⁡(PI)\operatorname{rec}(P)=\operatorname{rec}(P_I) because PI≠∅P_I\ne\varnothing [17]. Hence conv⁡(ZB)+rec⁡(P)⊆PI\operatorname{conv}(Z_B)+\operatorname{rec}(P)\subseteq P_I, proving (13).

By (12) and (13), an inequality α⊤y≤β\alpha^\top y\le\beta is valid for PIP_I if and only if

α⊤z≤β(z∈ZB),α⊤e≤0(e∈E).\alpha^\top z\le\beta\quad(z\in Z_B),\qquad\alpha^\top e\le0\quad(e\in E).

These inequalities define a cone in the n+1n+1 variables (α,β)(\alpha,\beta). Each coordinate of z∈ZBz\in Z_B is an integer of absolute value at most BB. The coordinate bound following (12) and the definition of BB imply that B≤2O(N2)B\le2^{O(N^2)} and ∥e∥∞≤2O(N2)\lVert e\rVert_\infty\le2^{O(N^2)} for every e∈Ee\in E. Thus each coefficient of this system has O(N2)O(N^2) bits. By (11), this cone has a finite set of integer generators with O(N3)O(N^3) bits per coordinate. The corresponding inequalities describe PIP_I. Indeed, by separation, every point outside PIP_I 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 g(y)=c⊤y+c0g(y)=c^\top y+c_0, where g≤0g\le0 is one of these defining inequalities and gg is positive somewhere on PP. Validity on PIP_I implies c⊤r≤0c^\top r\le0 for every r∈rec⁡(PI)=rec⁡(P)r\in\operatorname{rec}(P_I)=\operatorname{rec}(P). Thus (12) implies max⁡Pg=max⁡v∈Vg(v)\max_{P}g=\max_{v\in V}g(v). The coefficients of gg have O(N3)O(N^3) bits, and ∥v∥∞≤2O(N2)\lVert v\rVert_\infty\le2^{O(N^2)} for every v∈Vv\in V. Since n≤Nn\le N, it follows that log⁡2(1+H0)=O(N3)\log_2(1+H_0)=O(N^3). To bound the retained slacks, apply the same construction to K=P∩{g≥0}K=P\cap\{g\ge0\}. Its homogenized cone has n+1n+1 variables, and the additional inequality g≥0g\ge0 has O(N3)O(N^3) bits per coefficient. By (11), KK therefore has

point generators with O(N4) bits per coordinate.(14)\text{point generators with }O(N^4)\text{ bits per coordinate}. \tag*{(14)}

For each i∈Ji \in J, Lemma 1 shows that Bi=max⁡KsiB_i=\max_{K}s_i is attained at one of these point generators. Since si(y)=bi+1−aiTys_i(y)=b_i+1-a_i^{\mathsf T}y has O(N)O(N) bits per coefficient, (14) implies log⁡Bi=O(N4)\log B_i=O(N^4). If P≠∅P\ne\varnothing and PI=∅P_I=\varnothing, take g≡1g\equiv1. Then H0=1H_0=1 and K=PK=P, so the bound on BiB_i follows directly from the point-generator bound following (12). □\square

Proof of Theorem 1. Suppose PI≠∅P_I\ne\varnothing, and let g(y)=cTy+c0g(y)=c^{\mathsf T}y+c_0, where g≤0g\le0 is a defining inequality from Lemma 4 that is violated on PP. Since g≤0g\le0 on PIP_I and g>0g>0 somewhere on PP, we have c≠0c\ne0. The split (c,−c0)(c,-c_0) has branches g≤0g\le0 and g≥1g\ge1. To enforce g≤0g\le0 in one split round, it therefore suffices to reach a relaxation on which g<1g<1.

Let H0=⌈max⁡Pg⌉H_0=\lceil\max_{P}g\rceil and Hν=H0/2νH_\nu=H_0/2^\nu. We claim that g≤Hνg\le H_\nu on SCνb(P)\mathrm{SC}^{\nu b}(P) for every ν≥0\nu\ge0. At ν=0\nu=0, this follows from the definition of H0H_0. Suppose the claim holds at ν\nu. Apply Lemma 3 with Q=SCνb(P)Q=\mathrm{SC}^{\nu b}(P) and H=HνH=H_\nu. Then g≤Hν/2=Hν+1g\le H_\nu/2=H_{\nu+1} on SCb(Q)=SC(ν+1)b(P)\mathrm{SC}^{b}(Q)=\mathrm{SC}^{(\nu+1)b}(P). The number b=1+⌊4Δ/γ⌋b=1+\lfloor4\Delta/\gamma\rfloor is the same at each application: the retained rows JJ and their slack maxima BiB_i in (5) are determined by PP and gg, and γ\gamma in (6) depends only on nn. This proves the claim. For a=1+⌊log⁡2H0⌋a=1+\lfloor\log_2 H_0\rfloor, we have 2a>H02^a>H_0. Thus g≤Ha<1g\le H_a<1 on SCab(P)\mathrm{SC}^{ab}(P), and the split (c,−c0)(c,-c_0) enforces g≤0g\le0 in round ab+1ab+1.

We now bound ab+1ab+1 in terms of the input length, uniformly over the defining inequalities of PIP_I. Lemma 4 implies log⁡2(1+H0)=O(N3)\log_2(1+H_0)=O(N^3), so a=O(N3)a=O(N^3). To bound bb, recall from (5) that Δ=log⁡5+∑i∈Jlog⁡Bi\Delta=\log5+\sum_{i\in J}\log B_i. There are at most mm terms in the sum, each O(N4)O(N^4) by Lemma 4, so Δ=O(mN4)\Delta=O(mN^4). By (2) and (6), γ−1=32(12n)2\gamma^{-1}=32(12n)^2. Thus b=1+⌊4Δ/γ⌋=O(mn2N4)b=1+\lfloor4\Delta/\gamma\rfloor=O(mn^2N^4). The dense input records all mnmn matrix entries, so mn≤Lmn\le L. Since n≤Nn\le N, we have mn2≤Ln≤N2mn^2\le Ln\le N^2. It follows that each halving uses O(N6)O(N^6) rounds and that ab+1=O(N9)ab+1=O(N^9). The constants are uniform over the defining rows. Hence there is an integer R=O(N9)R=O(N^9) such that every row holds on SCR(P)\mathrm{SC}^{R}(P). Indeed, rows valid on PP remain valid throughout, and a row derived at round r≤Rr\le R holds on SCR(P)⊆SCr(P)\mathrm{SC}^{R}(P)\subseteq\mathrm{SC}^{r}(P). Since these inequalities define PIP_I, we have SCR(P)⊆PI\mathrm{SC}^{R}(P)\subseteq P_I. Conversely, every split cut preserves all integer points of PP and therefore their convex hull PIP_I. Thus SCR(P)=PI\mathrm{SC}^{R}(P)=P_I.

Suppose P≠∅P\ne\varnothing and PI=∅P_I=\varnothing. Since PP contains no integer point, the inequality g≤0g\le0 with g≡1g\equiv1 is valid at every integer point of PP. Apply Lemma 3 with Q=PQ=P and H=1H=1. After bb rounds, every point of SCb(P)\mathrm{SC}^{b}(P) must satisfy g≤1/2g\le1/2. Since g≡1g\equiv1, this closure is empty. Lemma 4 bounds log⁡Bi\log B_i by O(N4)O(N^4) also in this case, so the same estimate b=O(N6)b=O(N^6) applies. If P=∅P=\varnothing, then P=PIP=P_I before any round. □\square

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 ℓx\ell_x in (8) depend on F(x)F(x) and ∇F(x)\nabla F(x) and can be irrational. The strict bounds in (9) and (10) allow us to round these coefficients: at xx, the cut value exceeds γ\gamma, while on either branch at nonnegative height it is at most −2γ-2\gamma. We will use these bounds to construct a rational inequality that still excludes xx and is valid on both branches of the same split. The precision used in this rounding must therefore be uniform over the points xx, defining rows, and rounds.

Proposition 1. There is a polynomial pp such that O((L+1)9)O((L+1)^9) rounds suffice to reach PIP_I 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 p(L)p(L).

Proof. Let xx be a point in the current relaxation with g(x)≥0g(x)\ge0 that violates (7) at index j+1j+1, so that

F(x)+(j+1)γϕ(x)>0.(15)F(x)+(j+1)\gamma\phi(x)>0. \tag*{(15)}

We first bound the encoding length of the normal π=DxTu\pi= D_x^{\mathsf T}u of the split chosen at xx. By (2),

η∥u∥2≤dist⁡(πTx,Z)≤12.\eta\lVert u\rVert_2 \le\operatorname{dist}(\pi^{\mathsf T}x,\mathbb{Z}) \le\frac{1}{2}.

Since η=1/(12n)\eta= 1/(12n), we have ∥u∥2≤6n\lVert u\rVert_2 \le6n. For the llth coordinate vector ele_l, Cauchy–Schwarz implies

∣πl∣=∣⟨u,Dxel⟩∣≤6n∥Dxel∥2.|\pi_l| = |\langle u,D_xe_l\rangle| \le6n\lVert D_xe_l\rVert_2.

Let MM be the largest absolute entry among the retained row normals and cc. The column DxelD_xe_l has one entry ail/si(x)a_{il}/s_i(x) for each i∈Ji \in J and one entry cl/(g(x)+h)c_l/(g(x)+h), from the height term, for a total of ∣J∣+1|J|+1 entries. Each si(x)≥1s_i(x) \ge1. Each halving starts with H≥1H \ge1, so g(x)+h≥H/4≥1/4g(x)+h \ge H/4 \ge1/4. Thus every entry has absolute value at most 4M4M, and

∥Dxel∥22=∑i∈J(ailsi(x))2+(clg(x)+h)2≤(∣J∣+1)(4M)2.\lVert D_xe_l\rVert_2^2 = \sum_{i\in J}\left(\frac{a_{il}}{s_i(x)}\right)^2+\left(\frac{c_l}{g(x)+h}\right)^2 \le(|J|+1)(4M)^2.

Since ∣J∣≤m|J| \le m, it follows that ∣πl∣≤24nMm+1|\pi_l| \le24nM\sqrt{m}+1. Each aila_{il} has O(N)O(N) bits by the input bound, and each clc_l has O(N3)O(N^3) bits by Lemma 4. Hence log⁡2(1+M)=O(N3)\log_2(1+M) = O(N^3). As m,n≤Nm,n \le N, each integer πl\pi_l requires O(N3)O(N^3) bits, and the nn coordinates of π\pi together require O(N4)O(N^4) bits.

It remains to bound the split offset k=⌊πTx⌋k = \lfloor\pi^{\mathsf T}x\rfloor. Although K=P∩{g≥0}K = P \cap\{g \ge0\} can be unbounded, πTy\pi^{\mathsf T}y is constant along each recession direction of KK. Indeed, for every r∈rec⁡(K)r \in\operatorname{rec}(K), the proof of Lemma 1 establishes aiTr=0a_i^{\mathsf T}r = 0 for all i∈Ji \in J and cTr=0c^{\mathsf T}r = 0. Hence Dxr=0D_xr = 0 and πTr=⟨u,Dxr⟩=0\pi^{\mathsf T}r = \langle u,D_xr\rangle= 0. If VKV_K denotes the set of point generators in (14), then K=conv⁡(VK)+rec⁡(K)K = \operatorname{conv}(V_K) + \operatorname{rec}(K). Since x∈Kx \in K,

∣πTx∣≤max⁡v∈VK∣πTv∣≤n∥π∥∞max⁡v∈VK∥v∥∞.|\pi^{\mathsf T}x| \le\max_{v\in V_K}|\pi^{\mathsf T}v| \le n\lVert\pi\rVert_\infty\max_{v\in V_K}\lVert v\rVert_\infty.

Each coordinate of π\pi has O(N3)O(N^3) bits, and each coordinate of v∈VKv \in V_K has O(N4)O(N^4) bits by (14). Since ∣k∣≤∣πTx∣+1|k| \le|\pi^{\mathsf T}x|+1, the offset requires O(N4)O(N^4) bits as well.

We next round the coefficients of ℓx\ell_x. Rounding the coefficient of yly_l by ϵ\epsilon changes the cut value by ϵyl\epsilon y_l, for which there need not be a uniform bound on KK. Figure 5 illustrates how rounding in the original coordinates can exclude an integer point. The slacks in (4), however, satisfy 1≤si(y)≤Bi1\le s_i(y)\le B_i and 1≤t(y)≤51\le t(y)\le5 whenever y∈Py\in P and 0≤g(y)≤H0\le g(y)\le H. We therefore express ℓx\ell_x in these variables. For each slack ss, its contribution to the tangent Tx(y)T_x(y) is −log⁡s(x)+1−s(y)/s(x)-\log s(x)+1-s(y)/s(x). Summing over the ∣J∣+1|J|+1 slacks and substituting ϕ(y)=t(y)/4−1/2\phi(y)=t(y)/4-1/2 into (8), we obtain

Diagram comparing rounding in the original coordinates and in the slack

Figure 5. Rounding the same split cut to the nearest quarter. In coordinates u=y2u=y_2, v=2y2−y1v=2y_2-y_1, the strip is 0≤v≤3/40\le v\le3/4 and the original cut is 23v−13≤0\frac{2}{3}v-\frac{1}{3}\le0 (dashed boundary). Shading shows what each rounded cut retains. On the left, rounding in the original coordinates gives 3v≤u+13v\le u+1, which loses the integer point z=(−2,0)z=(-2,0) and retains x=(2,23)x=(2,\frac{2}{3}). On the right, with s=1+vs=1+v, the cut is 23s−1≤0\frac{2}{3}s-1\le0. Rounding gives v≤13v\le\frac{1}{3}, retaining the entire branch v=0v=0 and excluding xx.

ℓx(y)=Cx−∑i∈Jsi(y)si(x)+(jγ4−1t(x))t(y),(16)\ell_x(y)=C_x-\sum_{i\in J}\frac{s_i(y)}{s_i(x)}+\left(\frac{j\gamma}{4}-\frac{1}{t(x)}\right)t(y), \tag*{(16)}
Cx=F(x)+∣J∣+1+2γ−jγ/2.C_x=F(x)+|J|+1+2\gamma-j\gamma/2.

Round the constant and each coefficient of si(y)s_i(y) and t(y)t(y) in (16) to a nearest multiple of 2−q2^{-q}. Let δ0,δi,δt\delta_0,\delta_i,\delta_t denote the rounded value minus the original value for the constant, the coefficient of si(y)s_i(y), and the coefficient of t(y)t(y), respectively. Consecutive multiples of 2−q2^{-q} are 2−q2^{-q} apart, so each rounding error has absolute value at most 2−q/22^{-q}/2. The weaker bound 2−q2^{-q} will suffice. For the resulting affine function ℓ~x\widetilde{\ell}_x, subtracting (16) gives

ℓ~x(y)−ℓx(y)=δ0+∑i∈Jδisi(y)+δtt(y).\widetilde{\ell}_x(y)-\ell_x(y)=\delta_0+\sum_{i\in J}\delta_i s_i(y)+\delta_t t(y).

If y∈Py\in P and 0≤g(y)≤H0\le g(y)\le H, then y∈Ky\in K, so 1≤si(y)≤Bi1\le s_i(y)\le B_i for each i∈Ji\in J. Also, t(y)=1+g(y)/h≤1+H/h=5t(y)=1+g(y)/h\le1+H/h=5, since h=H/4h=H/4. By the triangle inequality,

∣ℓ~x(y)−ℓx(y)∣≤∣δ0∣+∑i∈J∣δi∣si(y)+∣δt∣t(y)\left|\widetilde{\ell}_x(y)-\ell_x(y)\right|\le|\delta_0|+\sum_{i\in J}|\delta_i|s_i(y)+|\delta_t|t(y)
≤2−q+∑i∈J2−qBi+5⋅2−q=2−q(6+∑i∈JBi).(17)\le2^{-q}+\sum_{i\in J}2^{-q}B_i+5\cdot2^{-q}=2^{-q}\left(6+\sum_{i\in J}B_i\right). \tag*{(17)}

We choose qq so that the error in (17) is at most γ/4\gamma/4. This preserves the strict signs in (9) and (10): a value greater than γ\gamma remains greater than 3γ/43\gamma/4, and a value at most −2γ-2\gamma remains at most −7γ/4-7\gamma/4. The required inequality is

2−q(6+∑i∈JBi)≤γ4,2^{-q}\left(6+\sum_{i\in J}B_i\right)\le\frac{\gamma}{4},

or equivalently 2q≥4(6+∑i∈JBi)/γ2^q\ge4(6+\sum_{i\in J}B_i)/\gamma. Taking the base-two logarithm and rounding up, we may therefore choose

q=⌈log⁡2(4(6+∑i∈JBi)γ)⌉.q=\left\lceil\log_2\left(\frac{4(6+\sum_{i\in J}B_i)}{\gamma}\right)\right\rceil.

We now verify that ℓ~x≤0\widetilde{\ell}_x\le0 is valid on both branches of (π,k)(\pi,k) and excludes xx. By (9) and (17), ℓ~x(x)>3γ/4\widetilde{\ell}_x(x)>3\gamma/4. By (10) and (17), ℓ~x(y)≤−7γ/4\widetilde{\ell}_x(y)\le-7\gamma/4 at every branch point yy of nonnegative height in the current relaxation. The same bound holds on P∩{g=0}P\cap\{g=0\}, since ℓx≤−2γ\ell_x\le-2\gamma throughout that section. Now suppose a branch point yy with g(y)<0g(y)<0 satisfies ℓ~x(y)>0\widetilde{\ell}_x(y)>0. Since g(x)>0g(x)>0, the segment [x,y][x,y] meets P∩{g=0}P\cap\{g=0\} at some point ww. The affine function ℓ~x\widetilde{\ell}_x is positive at both endpoints, so ℓ~x(w)>0\widetilde{\ell}_x(w)>0, 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 CC such that Bi≤2CN4B_i\le2^{CN^4} for every i∈Ji\in J. Since ∣J∣≤N|J|\le N, we have ∑i∈JBi≤N2CN4\sum_{i\in J}B_i\le N2^{CN^4}. Substituting this estimate and γ−1=O(N2)\gamma^{-1}=O(N^2) into the choice of qq following (17), we obtain

q≤1+log⁡2(4γ)+log⁡2(6+N2CN4)=O(N4).q\le1+\log_2\left(\frac{4}{\gamma}\right)+\log_2\left(6+N2^{CN^4}\right)=O(N^4).

We also need to bound the magnitude of each coefficient before rounding. Since j≤b−1=⌊4Δ/γ⌋j\le b-1=\lfloor4\Delta/\gamma\rfloor, we have jγ≤4Δj\gamma\le4\Delta. The coefficient of si(y)s_i(y) in (16) has absolute value 1/si(x)≤11/s_i(x)\le1. The coefficient of t(y)t(y) has absolute value at most jγ/4+1/t(x)≤Δ+1j\gamma/4+1/t(x)\le\Delta+1. For the constant term, (5) implies ∣F(x)∣≤Δ|F(x)|\le\Delta, so

∣Cx∣≤∣F(x)∣+∣J∣+1+2γ+jγ/2≤3Δ+∣J∣+3,|C_x|\le|F(x)|+|J|+1+2\gamma+j\gamma/2\le3\Delta+|J|+3,

where γ≤1\gamma\le1. Thus 3Δ+∣J∣+33\Delta+|J|+3 bounds the magnitude of every coefficient in (16). Rounding a coefficient α\alpha to a nearest multiple A/2qA/2^q means choosing an integer AA nearest to 2qα2^q\alpha. Hence

∣A∣≤2q∣α∣+12≤2q(3Δ+∣J∣+3)+1.|A|\le2^q|\alpha|+\frac12\le2^q(3\Delta+|J|+3)+1.

Since Δ=O(N5)\Delta=O(N^5), ∣J∣≤N|J|\le N, and q=O(N4)q=O(N^4), each such integer AA requires O(N4)O(N^4) bits.

It remains to express the rounded cut in the original variables. Denote its integer numerators by A0,Ai,AtA_0,A_i,A_t, so that

2qℓ~x(y)=A0+∑i∈JAisi(y)+Att(y).2^q\widetilde{\ell}_x(y)=A_0+\sum_{i\in J}A_i s_i(y)+A_t t(y).

At halving ν\nu, we have h=H0/2ν+2h=H_0/2^{\nu+2}. Substituting si(y)=bi+1−ai⊤ys_i(y)=b_i+1-a_i^\top y and t(y)=1+g(y)/ht(y)=1+g(y)/h, we obtain

2qH0ℓ~x(y)=H0(A0+At+∑i∈JAi(bi+1))+2ν+2Atc0+(2ν+2Atc−H0∑i∈JAiai)⊤y.\begin{aligned} 2^qH_0\widetilde{\ell}_x(y) &=H_0\left(A_0+A_t+\sum_{i\in J}A_i(b_i+1)\right)+2^{\nu+2}A_t c_0\\ &\quad+\left(2^{\nu+2}A_t c-H_0\sum_{i\in J}A_i a_i\right)^\top y. \end{aligned}

Every quantity on the right has integer coefficients. The factors H0H_0 and 2ν+22^{\nu+2} each require O(N3)O(N^3) bits, since Lemma 4 bounds log⁡2(1+H0)\log_2(1+H_0) by O(N3)O(N^3) and ν≤⌊log⁡2H0⌋\nu\le\lfloor\log_2 H_0\rfloor. The input coefficients ai,bia_i,b_i require O(N)O(N) bits per entry, and c,c0c,c_0 require O(N3)O(N^3) bits per entry by Lemma 4. Each product in the display requires O(N4)O(N^4) bits. Each coefficient is a sum of O(N)O(N) such products, so it also requires O(N4)O(N^4) bits. Since 2qH0>02^qH_0>0, the inequality 2qH0ℓ~x(y)≤02^qH_0\widetilde{\ell}_x(y)\le0 defines the same halfspace as ℓ~x(y)≤0\widetilde{\ell}_x(y)\le0. Its n+1n+1 integer coefficients therefore require O(N5)O(N^5) bits in total.

Choose a polynomial p(L)p(L) that bounds the encoding lengths of the rounded cuts and their justifying splits for every defining row g≤0g\le0, and also for g≡1g\equiv1 when PI=∅P_I=\varnothing. By Lemma 4, we may choose the same polynomial to cover the final cut g≤0g\le0 and its split (c,−c0)(c,-c_0) when c≠0c\ne0. Let R0=PR_0=P. For each r≥0r\ge0, obtain Rr+1R_{r+1} by intersecting RrR_r with every cut that is valid on both branches of a split in RrR_r and for which the cut and the split each require at most p(L)p(L) bits. There are finitely many such pairs. Since these rounds impose only cuts of bounded length, RrR_r may contain points outside SC⁡(P)\operatorname{SC}(P). We therefore prove the halving bound directly on RrR_r.

Fix gg and suppose a halving starts at RsR_s, with g≤Hg\le H throughout RsR_s. We prove by induction on jj, for 0≤j≤b0\le j\le b, that

F(y)+jγϕ(y)≤0for every y∈Rs+j with g(y)≥0.F(y)+j\gamma\phi(y)\le0\qquad\text{for every }y\in R_{s+j}\text{ with }g(y)\ge0.

At j=0j=0, this follows from (5). Suppose the bound holds at j<bj<b, and let x∈Rs+jx\in R_{s+j} satisfy g(x)≥0g(x)\ge0 and F(x)+(j+1)γϕ(x)>0F(x)+(j+1)\gamma\phi(x)>0. Since F(x)≤0F(x)\le0, we have ϕ(x)>0\phi(x)>0, so g(x)>hg(x)>h and the split in (2) applies. For every y∈Rs+jy\in R_{s+j} on either branch with g(y)≥0g(y)\ge0, we also have g(y)≤Hg(y)\le H, since Rs+j⊆RsR_{s+j}\subseteq R_s. Equations (2), (6), and (8), together with the induction hypothesis on Rs+jR_{s+j}, imply

ℓx(y)≤F(y)+jγϕ(y)−2γ≤−2γ.\ell_x(y)\le F(y)+j\gamma\phi(y)-2\gamma\le-2\gamma.

Thus (17) ensures that the rounded cut holds at these branch points.

Let y∈Rs+jy\in R_{s+j} lie on either branch with g(y)<0g(y)<0. By (9) and (17), ℓ~x(x)>3γ/4\widetilde{\ell}_x(x)>3\gamma/4. If ℓ~x(y)>0\widetilde{\ell}_x(y)>0, then ℓ~x\widetilde{\ell}_x is positive throughout [x,y][x,y] because it is affine. Since g(x)>0>g(y)g(x)>0>g(y), this segment contains a point w∈Pw\in P with g(w)=0g(w)=0. But (3), (6), and (8) imply ℓx(w)≤−2γ\ell_x(w)\le-2\gamma, so (17) implies ℓ~x(w)≤−7γ/4\widetilde{\ell}_x(w)\le-7\gamma/4, a contradiction. Thus the rounded inequality is valid on both branches of the chosen split in Rs+jR_{s+j} and excludes xx. Since both the cut and its split satisfy the length bound p(L)p(L), this cut is imposed in forming Rs+j+1R_{s+j+1}, so x∉Rs+j+1x\notin R_{s+j+1}. This proves the induction step.

Suppose y∈Rs+by\in R_{s+b} satisfies g(y)≥H/2g(y)\ge H/2. Then ϕ(y)≥1/4\phi(y)\ge1/4, so the induction bound at j=bj=b and the lower bound in (5) imply

−Δ≤F(y)≤−bγϕ(y)≤−bγ4<−Δ,-\Delta\le F(y)\le-b\gamma\phi(y)\le-\frac{b\gamma}{4}<-\Delta,

where the strict inequality follows from b>4Δ/γb>4\Delta/\gamma. Thus g<H/2g<H/2 throughout Rs+bR_{s+b}, and we can begin the next halving with upper bound H/2H/2. For each defining inequality g≤0g\le0 violated on PP, the proof of Theorem 1 bounds the number of halvings by O(N3)O(N^3) and the rounds per halving by O(N6)O(N^6).

Once g<1g < 1, the split on gg enforces g≤0g \le0 in one further round. Both this cut and its split satisfy the length bound p(L)p(L). Taking the maximum of these round counts over the defining inequalities, we obtain Rr=PIR_r = P_I for some r=O(N9)r = O(N^9). If P≠∅P \ne\varnothing and PI=∅P_I = \varnothing, one halving with g≡1g \equiv1 and H=1H = 1 forces Rb=∅R_b = \varnothing. If P=∅P = \varnothing, then R0=PIR_0 = P_I. 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. [1]Egon Balas, Disjunctive programming: properties of the convex hull of feasible points, Discrete Applied Mathematics 89 (1998), 3–44.DOI
  2. [2]Wojciech Banaszczyk, New bounds in some transference theorems in the geometry of numbers, Mathematische Annalen 296 (1993), 625–635.
  3. [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. [4]———, Complexity of branch-and-bound and cutting planes in mixed-integer optimization, Mathematical Programming 198 (2023), no. 1, 787–810.
  5. [5]Avinash Bhardwaj and Vishnu Narayanan, Split cuts in fixed integer dimensions, arXiv:2611.02169v2, 2026.arxiv.org/abs/2611.02169
  6. [6]Stephen Boyd and Lieven Vandenberghe, Convex optimization, Cambridge University Press, 2004.
  7. [7]Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli, Integer programming, Graduate Texts in Mathematics, vol. 271, Springer, 2014.
  8. [8]Michele Conforti, Alberto Del Pia, Marco Di Summa, and Yuri Faenza, Reverse split rank, Mathematical Programming 154 (2015), 273–303.
  9. [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. [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. [11]William Cook, Ravi Kannan, and Alexander Schrijver, Chvátal closures for mixed integer programming problems, Mathematical Programming 47 (1990), 155–174.DOI
  12. [12]Gérard Cornuéjols and Yanjun Li, On the rank of mixed 0,1 polyhedra, Mathematical Programming 91 (2002), 391–397.
  13. [13]Sanjeeb Dash, On the complexity of cutting-plane proofs using split cuts, Operations Research Letters 38 (2010), no. 2, 109–114.
  14. [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. [15]Johan Håstad, Dual vectors and lower bounds for the nearest lattice point problem, Combinatorica 8 (1988), 75–81.DOI
  16. [16]Alexander Schrijver, On cutting planes, Annals of Discrete Mathematics 9 (1980), 291–296.
  17. [17]———, Theory of linear and integer programming, John Wiley & Sons, 1986.

Paper details

vlnc:W_92pr2eeq
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