How Much of the Split Closure Do Small Lifted Cuts Actually Capture?

Integer programming solvers work by first ignoring the requirement that variables be whole numbers, solving the easier continuous problem, and then adding cutting planes: extra linear inequalities that slice off fractional solutions without removing any integer ones. Theory has a precise description of one important family of these cuts. Basu and Molinaro showed that the split closure, meaning everything left after applying every possible split cut at once, is captured exactly by "α-cuts." To build one, you take an integer-weighted combination α of rows of the simplex tableau (the solver's current linear system) and apply the standard Gomory mixed-integer rounding formula to that combination. The catch is that α ranges over an infinite set. The paper gives no rule for choosing it and reports no experiments. Nobody knows whether a handful of α vectors with tiny support recover most of the split closure on real instances, or almost none of it.

This note proposes to find out. We will build a separator restricted to α-cuts with small, structured weight vectors, and measure three things against the exact split-closure bound: how much of the gap it closes, how dense the resulting cuts are, and whether they are numerically safe. We will then test whether any of this survives inside a full branch-and-cut solver, where extra cuts slow down the linear program solves. The theory makes sharp predictions we can check. It says single-row cuts are nearly enough on packing and covering problems but can be arbitrarily weak on general mixed-integer programs. If those predictions hold on standard benchmarks, we learn where lifting theory pays off in practice. If they fail, we learn that the theory has been measuring the wrong thing.

Core Claim

Our hypothesis is that choosing α to cancel columns across tableau rows produces cuts that are both stronger and sparser than single-row Gomory cuts. In the aggregated row, a nonbasic variable that appears in two rows with opposite signs drops out, so it gets no coefficient in the cut. This is exactly the "variable cancellation" mechanism that Theoretical challenges towards cutting-plane selection identifies as the reason single-row closures can be arbitrarily worse than aggregation closures on general mixed-integer programs. If the hypothesis holds, it softens the tension that paper also documents: in one reported experiment, adding nine dense valid cuts increased solve time by 25%. It softens it because the cuts that the theory says are strong would also be the cheap, sparse ones.

Concretely, write the tableau rows as $x_{B_i} + \sum_j \bar a_{ij} x_j = \bar b_i$. For an integer vector $\alpha$, the α-cut applies the Gomory mixed-integer function to the aggregated row $\sum_i \alpha_i x_{B_i} + \sum_j (\alpha^\top \bar a_j)\, x_j = \alpha^\top \bar b$. Here $\bar a_j$ is column $j$ of the tableau and $\bar b$ is its right-hand side. We restrict α to at most $s$ nonzero entries, each in $\{-M,\dots,M\}$, and we choose it so as to zero out many entries of $\alpha^\top \bar a_j$. The empirical claim is that small $s$ (two or three) and $M = 1$ already recover most of the split-closure bound wherever cancellation structure exists. We further claim that a cheap instance statistic, the fraction of nonbasic columns cancellable by a pair of rows, predicts where that recovery happens.

Relation to Prior Work

Two strands of prior work motivate this project. Characterization of the split closure via geometric lifting supplies the cut family and the guarantee that α-cuts dominate every split cut. It leaves the selection of α open and contains no experiments. How Good Are Sparse Cutting-Planes? proves that sparse cuts can fail badly in the original space yet succeed after lifting, but it validates this only on random 0/1 polytopes with $n=10$. We take their distance-based view of sparsity as the lens for asking whether aggregated cuts stay sparse. The polyhedrality results in On the Chvátal-Gomory closure of a compact convex set, A short proof for the polyhedrality of the Chvátal-Gomory closure of a compact convex set and The split closure of a strictly convex body act as a constraint rather than a method. They tell us finitely many cuts suffice in the rational polyhedral case, which is what makes a finite "fraction of closure captured" measure meaningful. They also warn that this assumption breaks outside that setting, so we restrict to linear instances.

The machine-learned cut selectors form the competing empirical line. Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model (HEM) learns which cuts to add, how many, and in what order, at the root node. Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming extends selection to every node of the search tree. MIRACLE imitates SCIP's own selector and then refines it with reinforcement learning. All three choose among cuts that the solver already generates. We change which cuts get generated, and we hold the selector fixed. The two ideas are complementary, but they must be separated experimentally, because a reviewer could reasonably suspect that selection, not generation, is the bottleneck.

Research Program

The first component is offline and exact. On instances small enough to allow it, we compute the split-closure bound $z_{\text{split}}$ by repeatedly solving a mixed-integer separation problem. We report, for each α-family, the gap-closed fraction

$$\rho = \frac{z_\alpha - z_{LP}}{z_{\text{split}} - z_{LP}},$$

where $z_{LP}$ is the continuous relaxation bound and $z_\alpha$ is the bound after running the restricted α separator to a fixed point. This quantity directly answers the question Basu and Molinaro leave open. We sweep the support size $s$ and the entry bound $M$, and record cut density and the dynamic range of cut coefficients alongside $\rho$.

The second component is numerical. Every generated cut is checked in exact rational arithmetic against known feasible and optimal solutions. This counts how often floating-point α-aggregation produces an invalid cut, which is the numerical-safety frontier raised in Theoretical challenges towards cutting-plane selection. We expect invalid cuts to grow with $M$, and that would justify the small-entry restriction on grounds of safety as well as speed.

The third component is in-solver. The separator runs as a SCIP plugin through PySCIPOpt, using the same tooling stack as the MIRALab-USTC/L2O-G2MILP code. It runs first at the root only and then at all nodes. Its cuts go into SCIP's default selector, so any change is attributable to the cut pool.

Baselines

The naive reference point is SCIP with cuts disabled, and separately SCIP with only single-row Gomory cuts (α equal to a unit vector). The second is the direct "no lifting" control. Every gain we claim must first be a gain over single-row cuts produced by the same code path.

The strongest non-learned competitor is full SCIP default separation. That includes its mixed-integer rounding cuts, which already aggregate original constraint rows heuristically. It is the real threat, because it may already exploit much of the same cancellation structure. We run it with identical time limits, random seeds and hardware. The α separator must either raise $\rho$ over default SCIP at equal or lower cut density, or reduce the shifted geometric mean of solve time on instance classes where default SCIP leaves split-closure gap on the table.

The strongest learned competitors are the published selectors. The file reports that HEM achieved "a 40.77% improvement in the Primal-Dual gap integral compared to the 'No Cuts' baseline" on challenging MIPLIB instances. It also reports that Global Cut Selection achieved "a 43.9% reduction in solving time and a 31.8% reduction in the number of nodes explored compared to the SCIP default" on SetCover. MIRACLE reports "average 3.78× speedup on MIPLIB problems." There is no reported result found on Lacuna for split-closure gap closed by any α-cut or aggregated tableau-cut separator. We cannot rerun those systems exactly without their code. Instead, we report our primal-dual gap integral against no-cuts on the same MIPLIB 2017 subset, so the 40.77% figure serves as an external reference, not a head-to-head comparison.

Two ablations isolate the key ingredient. The first uses random α with the same support and entry bound. The second uses α chosen to maximize violation, ignoring cancellation. If cancellation-guided α beats both on the combination of $\rho$ and density, the mechanism is real rather than an artifact of simply having more cuts.

Why not just…?

Why not just rely on SCIP's existing aggregation cuts? Those cuts combine original constraints using a heuristic path search. They do not combine tableau rows chosen for cancellation, and nothing in the file measures how close they come to the split closure. This is a genuine threat. If default SCIP already achieves a $\rho$ near that of the α separator, the α separator has no practical advantage, and our contribution becomes the measurement itself. The offline $\rho$ comparison settles this directly.

Why not just improve selection with a learned model, as HEM, Global Cut Selection or MIRACLE do? A selector can only choose from the pool it is given. If the pool misses the cuts that close the split-closure gap, better selection cannot recover them. Distributional MIPLIB also documents an inference bottleneck: on OTS-Easy, SCIP reached a primal-dual integral of 20.0 while the ML-guided model reached 27.9 (Distributional MIPLIB). Holding the selector fixed while varying the pool shows which lever matters on each instance class.

Why not just stick to single-row cuts, which are sparse and safe? On covering problems this may be right. Theoretical challenges towards cutting-plane selection shows single-row cuts are nearly sufficient there, and we predict α-cuts add little on SetCover. On general mixed-integer programs, the same paper shows single-row closures can be arbitrarily worse. Our instance-class breakdown tests exactly this dichotomy.

Why not just add all generated α-cuts at once? HEM showed that the order and number of cuts added change performance even when the cut set is fixed. MIRACLE showed that hoarded cut pools inflate memory, reporting 3.03 GB on hard SetCover instances. That is why the pool goes through a standard selector rather than being dumped wholesale into the linear program.

Proposed Experiments

The offline $\rho$ study uses small MIPLIB 2017 instances plus the Easy tier of Distributional MIPLIB, where many instances are drawn from each distribution and results can be averaged. The in-solver study uses the MIPLIB subset from HEM, together with SetCover, MIK, CORLAT and Combinatorial Auctions as used by the learned selectors. Metrics are $\rho$, average cut density, the fraction of cuts that are invalid in exact arithmetic, root and total solve time, node count, and the primal-dual gap integral.

The decisive checks are three. First, on MIK and general mixed-integer MIPLIB instances, cancellation-guided α with $s \le 3$ and $M=1$ must reach a clearly higher $\rho$ than single-row Gomory cuts at no greater density. Second, on SetCover, that advantage should nearly vanish, matching the packing and covering theory. Third, across instances, the cancellation statistic should correlate with the advantage in $\rho$. If the first check fails, the theory's aggregation advantage does not show up in practice at small support. If the third fails, the proposed mechanism is wrong even where the gains are real. Either outcome is a publishable correction to how lifting theory is used to reason about solvers.