Exact Cut Separation Where the Fractional Support Is Small: Testing a Tractability Theorem on Non-Convex Bilinear Programs

Exact solvers for integer and non-convex problems repeatedly solve an easier continuous problem and then add cutting planes, linear inequalities that every true solution satisfies but the current relaxed solution violates. Finding the strongest such inequality, called the separation problem, is provably intractable for most of the useful families. Solvers therefore use fast heuristics and accept weaker cuts. One theoretical result offers a way around this. When the relaxed solution has only a few "fractional" coordinates, meaning coordinates that sit strictly between their bounds, exact separation becomes cheap: its cost grows exponentially in that small count and only polynomially in everything else. This result has never been implemented. Nobody knows whether real solver iterates actually have small fractional support, or whether it can be exploited for the non-convex relaxations where heuristics are currently the only option.

We propose to build exact separation routines whose running time is exponential only in the fractional-support size $\alpha$. We target two settings. The first is the lifted bilinear cover inequalities for non-convex separable bilinear programs, which today are separated only by a randomized heuristic. The second is the knapsack configuration inequalities, which serve as a calibration case. We will then measure three things inside a working branch-and-cut solver: how large $\alpha$ really is, how much violation the heuristics leave unfound, and whether exactness pays for its cost in wall-clock time. In two sentences: a theorem says exact cuts are cheap when few coordinates are fractional. We test whether that condition holds in practice and carry the idea over to non-convex bilinear relaxations, where nobody has an exact separator.

Core Claim

On the Complexity of Separation from the Knapsack Polytope proves NP-completeness of exact separation for extended cover, $(1,k)$-configuration and weight inequalities. It also shows that when the relaxation has a constant number $m$ of constraints, extreme points have at most $m$ fractional components. In that case, separation of generalized $(1,k)$-configurations runs in $O(n^2 \cdot 2^\alpha \cdot \log n \cdot m)$ time, where $n$ is the number of variables and $\alpha$ the number of fractional components. The paper contains no implementation.

Solving Sparse Separable Bilinear Programs Using Lifted Bilinear Cover Inequalities makes three contributions:

  • It proves that adding a semidefinite constraint to the McCormick relaxation (the standard linear envelope of each product $x_i y_j$) gives no bound improvement for separable bilinear sets.
  • It introduces lifted bilinear covers.
  • It separates them with a randomized heuristic, applied at the root node only and tested on synthetic instances.

The authors conjecture that the separation problem is NP-hard.

Our claim is that the support-parameterized argument carries over to bilinear covers, in a non-convex setting. Our candidate parameter is the number $\alpha$ of bilinear terms whose pair $(x_i, y_j)$ sits off a corner of its box at the current relaxed point. Variables at corners can be fixed when enumerating candidate covers and lifting coefficients, which leaves a search over subsets of the $\alpha$ "active" terms.

Whether this yields an exact algorithm with cost $2^\alpha \cdot \text{poly}(n)$ is the first theoretical deliverable. It is not assumed. McCormick vertices need not inherit the $\le m$ bound, because the envelope adds four inequalities per product. The size of $\alpha$ at real iterates is therefore an empirical question, and answering it is the second deliverable.

Research Program

The theoretical part has two goals. First, we characterize which lifted bilinear covers can be separated exactly by enumerating over the active-term set. Second, we give a matching hardness statement when $\alpha$ is unbounded, which would also settle the open conjecture of Gu et al. If exact lifting proves hard even for fixed $\alpha$, we fall back to exact cover selection with sequential lifting. We would state this weaker guarantee explicitly.

The engineering part implements both separators as compiled plugins in SCIP. They run at every node of the branch-and-cut tree, not only the root. Each separator has a dispatch rule: if $\alpha$ is below a budget, run the exact routine; otherwise run the existing heuristic. This keeps worst-case time bounded. We keep the plugins in compiled code because A Neural Separation Algorithm for the Rounded Capacity Inequalities and Distributional MIPLIB both document per-call overhead swamping algorithmic gains. Huang et al. report a primal-dual integral of 20.0 for default SCIP versus 27.9 for a model-guided solver on Optimal Transmission Switching (Easy), where lower is better.

The measurement part is the main empirical contribution. It does three things:

  • It logs the distribution of $\alpha$ at every separation call, per instance family.
  • It reports how often the exact routine finds a violated cut after the heuristic reported none.
  • It reports how much deeper the exact cut is.

Baselines

Do nothing. The weakest reference is the solver with its default cuts and no added family. For bilinear instances this is McCormick plus SCIP's built-in non-convex machinery. For knapsack instances it is SCIP's default lifted cover separator. This tells us whether either cut family matters at all on each distribution.

Randomized heuristic. The strongest existing competitor on the bilinear side is the randomized heuristic separator of Gu et al. It is the only published separator for lifted bilinear covers. They report that on non-negative synthetic instances it closes approximately 60% of the root gap, with separation taking only a few seconds. We reimplement it in the same plugin interface and regenerate instances following their described construction. Our exact routine must exceed it on root gap closed at matched separation time to count as a win. In branch-and-cut, it must also reduce time-to-optimality or the final gap within a fixed time limit.

On the knapsack side, the strongest competitor is SCIP's default cover and lifting separation. There is no reported result on Lacuna for the exact $(1,k)$-configuration separation of Del Pia et al. inside a solver, so that comparison is new.

Exact separation by integer program. We also solve each separation problem as a small integer program with a time limit. This yields cuts identical to ours when it finishes, so it isolates whether our support-parameterized enumeration is faster, not stronger.

Ablations. The key ablation runs the exact routine without the $\alpha$-dispatch, enumerating over all terms. This tests whether sparsity is what makes exactness affordable. A second ablation sweeps the $\alpha$ budget.

Fairness. All arms share the same instances, the same single-threaded SCIP build, identical time limits and the same cut-round limits. The heuristic receives restarts up to the exact routine's average time.

Why not just…?

Why not just give the randomized heuristic more restarts? If violated covers are plentiful, more restarts may find most of them, and exactness would add little. This is a real threat. The experiment settles it directly: for each call where the heuristic with its matched time budget reports no cut, we record whether the exact routine finds one, and how deep. If that rate is near zero, the honest conclusion is that the heuristic suffices, and our measurement still delivers the first evidence of that.

Why not just formulate separation as an integer program and let the solver handle it? This is the standard generic route to exact separation, and it produces the same cuts. Its weakness is overhead per call at every tree node. The integer-program baseline above measures this directly. If its time is comparable to ours at the observed values of $\alpha$, our contribution narrows to the hardness and characterization results, and we will say so.

Why not just learn the separator, as NeuralSEP does for routing? NeuralSEP, the graph neural network separator of Kim et al., beats the C heuristic library CVRPSEP on large routing instances, with an optimality gap of 22.8% versus 37.2% at 1,000 customers. However, the authors note higher latency per iteration than CVRPSEP's C implementation, and their model offers no exactness. Learned selection methods such as Learning to Cut by Looking Ahead and MIRACLE only filter cuts that heuristics already generated, so they cannot recover cuts the heuristic misses. If the $\alpha$ distribution turns out to be large, a learned separator becomes the natural next step, and our exact routine would supply its training labels.

Why not just tighten with a semidefinite relaxation? For separable bilinear sets, Gu et al. prove that a semidefinite constraint adds nothing over McCormick. This alternative is ruled out on this class by a theorem rather than by experiment.

Proposed Experiments

Bilinear arm. We use the synthetic sparse separable bilinear instances regenerated following Gu et al., in both their non-negative and mixed-sign variants. These are complemented by bilinear instances drawn from Distributional MIPLIB domains where products arise after modeling. If no such domain exists, we report results only on the synthetic set. There is no reported result on Lacuna for lifted bilinear covers on real-world instances.

Knapsack arm. We use the knapsack-rich distributions of Distributional MIPLIB across its hardness tiers, plus MIPLIB 2017.

Metrics. We report:

  • the histogram of $\alpha$ per family;
  • the fraction of calls where exact separation finds a cut the heuristic missed;
  • root gap closed;
  • separation time per call;
  • branch-and-cut solve time, node count and primal-dual integral at a fixed limit.

Decisive checks. The proposal succeeds only if three things hold. First, a substantial share of separation calls has small $\alpha$, under a threshold fixed before running. Second, on those calls the exact routine closes more root gap than the time-matched heuristic's roughly 60%. Third, full tree solves improve, rather than lose, wall-clock time against the heuristic and against the integer-program separator. If $\alpha$ is typically large, that result is still a definitive empirical answer to whether the Del Pia et al. tractability regime is realized in practice.