Integer programming solvers tighten a fractional linear relaxation by adding cutting planes, which are inequalities that every integer solution satisfies but the current fractional point violates. A classical source of cuts is a split: an integer direction $\pi$ and integer $\pi_0$ such that no integer point lies strictly between $\pi x = \pi_0$ and $\pi x = \pi_0 + 1$. Removing this slab from the relaxation and taking the convex hull of what remains gives a cut. Using $t$ slabs at once, called a $t$-branch split, removes more and should give stronger cuts. Dash, Günlük and Morán R. (On the Polyhedrality of Closures of Multibranch Split Sets and Other Polyhedra with Bounded Max-Facet-Width) proved that the closure under all $t$-branch splits of a rational polyhedron is again a polyhedron. Their proof is non-constructive, and the paper reports no computation. The result is that nobody in the literature we have examined knows whether these stronger closures help a real solver.
This note proposes that the obstacle is geometric and can be measured. Generating a cut from $t$ slabs means solving a linear program with one block of variables for each nonempty piece of the relaxation that is left after the slabs are removed. Naively there are $2^t$ such pieces. If the slabs are restricted to the low-dimensional space of a few fractional variables and the cut is then lifted back, the number of pieces is bounded by the cell count of an arrangement of $2t$ hyperplanes in that space. That bound is polynomial in $t$ and is usually far smaller in practice. We will build a separator that enumerates only the nonempty pieces, use the piece count as a cost signal for choosing which multibranch splits to try, and run the first benchmark study of multibranch split cuts on MIPLIB 2017 and Distributional MIPLIB.
Core Claim
The relaxation is $P$, and the $t$ slabs are $S_1,\dots,S_t$. A $t$-branch split cut is any valid inequality for $\mathrm{conv}(P \setminus \bigcup_i S_i)$. The set $P \setminus \bigcup_i S_i$ splits by sign pattern: each slab is avoided either on its left or on its right. Only the patterns whose region actually meets $P$ contribute a block to the cut-generating linear program. Call the number of such patterns $N(P,S_1,\dots,S_t)$, the piece count. It is a union-complexity quantity: it counts the faces of the region outside a union of slabs, which is the kind of quantity studied for unions of geometric objects.
Suppose the slab directions live in a $k$-dimensional space. This happens, for example, when they are integer combinations of $k$ tableau rows, as in the $\alpha$-cuts of Basu and Molinaro. The $2t$ bounding hyperplanes then form an arrangement in $\mathbb{R}^k$, and the standard arrangement bound (see Clarkson et al. for the $O(n^d)$ worst case) gives
$$N(P,S_1,\dots,S_t) \le \min\{2^t,\; O((2t)^k)\}.$$
When $k$ is 2 or 3, which is common for the corner relaxations used by Gomory-style cuts, this is polynomial. The stronger claim, which we will test empirically, is that on real instances the measured $N$ is close to linear in $t$.
The claim has three parts:
- The piece count can be computed cheaply by enumerating cells inside $P$, using only feasibility checks for the cells that actually appear.
- The piece count predicts the solve cost of each candidate cut.
- Choosing splits by gap closed per piece makes $t=2$ and $t=3$ split cuts affordable inside a branch-and-cut solver.
Where This Sits Relative to Prior Work
Three groups of papers play different roles.
The theory that motivates the work is the closure literature. Dadush, Dey and Vielma and Braun and Pokutta prove that Chvátal-Gomory closures of compact convex sets are polytopes. Dey and Vielma show that split closures of strictly convex bodies need not be polyhedral. Dash et al. extend polyhedrality to multibranch splits. All of these establish finiteness or its failure, but none gives a procedure or a cost model. We do not try to make the well-quasi-ordering argument of Dash et al. constructive. We sidestep it by bounding the cost of one cut rather than the size of the whole closure.
The lifting technique comes from Basu and Molinaro. They show that integer combinations $\alpha$ of tableau rows give exactly the split closure on corner relaxations, and they leave open how to choose $\alpha$. We reuse their construction as our candidate generator. Restricting $\alpha$ to small support is what keeps $k$ small and the arrangement bound meaningful. Their 3-variable pure-integer instance, where the split closure leaves a gap of at least $1/(12\epsilon)$, is our first sanity test. Dey, Molinaro and Wang show that sparse cuts in a lifted space can be much stronger than sparse cuts in the original space. This supports projecting to a small space and lifting back, and it warns that the lifted cut may become dense.
The empirical side constrains the design. Turner, Berthold and Besançon show that cuts with more than 40–50% nonzero entries almost always hurt SCIP, so any multibranch cut we add must pass their filters. MIRACLE reports that only 1–2% of candidate cuts help, which means candidate screening matters more than the strength of any single cut.
Bodur et al. prove that 1-row closures are within a factor of 2 of full aggregation closures for packing and covering programs. This predicts that multibranch cuts will gain little on pure packing and covering instances, so we use those instances as a negative control.
Finally, the geometric results on output-sensitive union computation (Agarwal and Steiger) and on lower union complexity under random sizes (Agarwal, Kaplan and Sharir) supply the intuition for our approach: pay only for the pieces that exist, and expect typical inputs to be far below the worst case. Their 3D box-sweeping algorithms do not apply directly to slabs in $\mathbb{R}^k$, so we borrow the output-sensitive principle and not the data structures.
Research Program
The first component is a SCIP separator, which will be released openly. At each root round it works in four steps:
- Take the $k \le 3$ most fractional basic variables.
- Generate candidate split directions as small-support integer combinations $\alpha$ of their tableau rows.
- Form $t$-tuples of candidates for $t \in \{1,2,3\}$.
- Enumerate the nonempty sign cells of each tuple inside the projected relaxation.
Cell enumeration is incremental: a cell is added only if a small feasibility LP confirms that its region meets the projected relaxation. This makes the work proportional to $N$ rather than to $2^t$. The cut-generating linear program is built over the surviving cells only, the resulting cut is lifted back to full space by the standard lift-and-project lifting, and the cut is passed through Turner et al.'s density and parallelism filters.
The second component is analytic. We will tighten the piece-count bound for slabs whose width is large relative to the projected relaxation, which is the slab analogue of "fat" objects. The conjecture is that $N = O(t)$ when every slab is at least as wide as a constant fraction of the region's width in its direction. We will try to prove this and also check it against the counts measured on instances.
The third component is a selection rule. Candidates are ranked by estimated gap closed divided by $N$. The gap estimate comes from the violation at the current point. This ranking is compared against ranking by violation alone.
Baselines
The naive reference point is default SCIP 8.0.3 on the same machines, with the same time limit and the same random seeds. Every result is reported as a ratio to this reference.
The strongest existing method for this question is Turner et al.'s context-aware cut selection in SCIP 8.0.3. On MIPLIB 2017 it reports a solve-time ratio of 0.95, a node ratio of 0.92, and 14 more instances solved than default, with parameters tuned by SMAC on a 40-instance training set. It is the right competitor because it is the best published account of making the solver's existing cuts pay off, and it already contains the filters our cuts must pass. We run their configuration as published, and our separator inherits that configuration so that only the candidate pool changes. Any extra parameters we introduce get the same 40-instance SMAC budget. Beating Turner et al. means a solve-time ratio below theirs on the MIPLIB 2017 benchmark set, measured against the same default reference, together with at least as many instances solved.
MIRACLE reports a 3.78× average speedup on MIPLIB. It optimizes selection among standard cuts, whereas we change which cuts exist, so the two approaches are complementary rather than direct competitors. We will try to reproduce MIRACLE if its code is available. If not, we report its figure as context only, because its evaluation subset differs from ours.
Two ablations isolate the key ingredient. The first builds the cut-generating LP over all $2^t$ sign patterns with no cell pruning, which measures what piece counting saves. The second sets $t=1$ with the same $\alpha$ generator, which measures what multibranch disjunctions add over ordinary lifted splits.
For root gap closed by multibranch split cuts on MIPLIB, we found no reported result on Lacuna.
Why not just…?
Why not just use one-branch splits and Gomory cuts, which solvers already do well? For pure packing and covering programs this is probably right. Bodur et al.'s factor-2 result predicts it, and we treat those instances as a control on which we expect no gain. For general integer programs, Basu and Molinaro's $1/(12\epsilon)$ instance shows that split closures can be nearly useless. Whether that weakness appears on MIPLIB is the question the $t=1$ ablation answers. If $t=2,3$ closes no more root gap than $t=1$ at equal cut counts, the proposal fails, and we will report that result.
Why not just branch, or take cuts from a shallow partial search tree? This is the most serious alternative. A depth-$t$ tree on variable disjunctions also yields a disjunctive cut-generating LP, and its leaf count can likewise be pruned by checking which leaves are feasible. We will run this as an extra baseline: disjunctive cuts from a depth-$t$ tree of variable branchings, with the same budget on the number of cells. Multibranch splits have to win specifically because general integer directions $\pi$ cut regions that variable branchings cannot. If they do not win, the contribution narrows to the piece-count cost model, and that model applies to tree disjunctions as well.
Why not just learn cut selection, as MIRACLE does? Learned selectors choose among cuts the solver already generates, so they cannot add a cut family that has no generator. Huang et al. also report that in-solver inference overhead can dominate on some distributions: on the Optimal Transmission Switching Easy distribution, the learned model's primal-dual integral was 27.9 against 20.0 for SCIP (Distributional MIPLIB). The piece count is a single cheap feature that any learned selector could use, and we will test whether it predicts per-cut solve time better than violation alone.
Why not just enumerate all $2^t$ terms, since $t \le 3$? At $t=3$ that is only 8 blocks per cut, so pruning may save little at the root. This is why the full-enumeration ablation exists. Pruning has to earn its place through measured time per cut and through enabling $t=4$ or $5$. If it does neither, we will report the selection rule as the contribution instead.
Proposed Experiments
The first check uses Basu and Molinaro's 3-variable instance and confirms that $t=2$ cuts close gap that the split closure cannot. Next we record the distribution of measured $N$ against $2^t$ and against the arrangement bound on MIPLIB 2017 and on Distributional MIPLIB, across its 35+ distributions and five hardness levels. This tests whether the piece count is typically near-linear in $t$, and whether the hardness levels separate on it.
The main measurements on both libraries are root gap closed and cut-generation time for $t \in \{1,2,3\}$, with and without pruning. End-to-end comparisons against default SCIP, Turner et al., and the shallow-tree baseline report solve-time ratio, node ratio, instances solved, and primal-dual integral. Packing and covering instances, including the market split instances from Bodur et al., are reported separately as the negative control. In those comparisons we also test whether the piece count predicts per-cut time.
The decisive outcome is $t \ge 2$ closing measurably more root gap than $t=1$ on general integer instances while keeping a solve-time ratio at or below Turner et al.'s 0.95 relative to default. If gap closed improves but time does not, the cut family is real and its cost model is the open problem.
References
- On the Polyhedrality of Closures of Multibranch Split Sets and Other Polyhedra with Bounded Max-Facet-Width
- Characterization of the split closure via geometric lifting
- Combinatorial complexity bounds for arrangements of curves and spheres
- 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
- The split closure of a strictly convex body
- How Good Are Sparse Cutting-Planes?
- A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming
- MIRACLE: Model-free Imitation and Reinforcement Learning for Adaptive Cut-Selection
- Aggregation-based cutting-planes for packing and covering integer programs
- An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D
- Union of Hypercubes and 3D Minkowski Sums with Random Sizes
- Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods