Does Synthetic MILP Data Reproduce the Cost of Cutting?

Machine-learned components inside integer-programming solvers are usually trained on synthetic problem instances, because real industrial instances are scarce and often proprietary. One of the most valuable of these components is the cut selector: the policy that decides which extra constraints to add so the solver's continuous relaxation more closely approximates the true integer problem. The work it has to do is a trade-off. Each added constraint, called a cutting plane, tightens the bound and prunes the search. It also makes every later linear-program solve denser, slower and more memory-hungry. When a problem is split into coupled pieces, as in decomposition methods, added constraints can also make the subproblems harder to solve.

Current instance generators are judged by whether their synthetic instances take about as long to solve as the real ones under default settings. We argue that this is the wrong test for any learned component whose job is managing that trade-off. What such a component needs from its training data is realistic sensitivity to added constraints: how much bound each extra round of cuts buys, and how much linear-algebra slowdown it costs. We propose to measure this sensitivity directly as an "overhead-response curve." We will test whether matching it, rather than matching solve time, predicts whether a cut policy trained on synthetic data works on real instances. We will also measure how many synthetic instances are worth one real one when the synthetic set is filtered for response fidelity.

Core Claim

Two synthetic instances can have the same default solve time and still react very differently to cuts. One may get large bound gains from a few sparse cuts. The other may clog after a handful of dense ones. Evidence that this reaction is where real solver cost lives comes from several places. Theoretical challenges towards cutting-plane selection surveys "clogging," where nine dense valid constraints raised total solve time by 25%. A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming gains its improvements by filtering cuts denser than 40% and capping added nonzeros. MIRACLE gets most of its speedup by throttling cuts, which reduced memory by 86.3% on average. The decomposition setting shows the same pattern. In Branch-and-cut-and-price for agile earth observation satellite scheduling, adding one family of cuts (subset-row inequalities) to the master problem enlarges the pricing dynamic program, and this makes easy instances slower overall. In Towards Accelerating Benders Decomposition via Reinforcement Learning Surrogate Models, the master problem gets slower as it accumulates cuts.

Generators, by contrast, are validated on other quantities. G2MILP, ACM-MILP and MILP-StuDio all report solve-time or node-count agreement, feasibility, or downstream gains for branching and solution prediction. None reports how synthetic instances respond to cuts. Our claim has two parts. First, response fidelity and solve-time fidelity come apart on standard generators. Second, response fidelity is the better predictor of how a synthetic-trained cut policy performs on real instances.

To make this concrete, fix a cut-aggressiveness setting $\theta$ from a small grid (maximum cuts per round combined with a nonzero budget). For an instance $x$, we record two quantities. The first is the root gap closed, $G(x,\theta)$, which is the fraction of the gap between the plain relaxation bound and the best known solution that the cuts remove. The second is the per-solve linear-program cost, $C(x,\theta)$, measured in simplex iterations and wall time after the cut rounds, relative to the no-cut setting. The response profile of $x$ is the curve $\theta \mapsto (G, \log C)$. Response fidelity of a synthetic set $S$ to a real set $R$ is

$$D_{\text{resp}}(S,R) = \frac{1}{|\Theta|}\sum_{\theta\in\Theta} W\big(P_S(G,\log C \mid \theta),\, P_R(G,\log C\mid\theta)\big),$$

where $\Theta$ is the grid of settings, $P_S$ and $P_R$ are the empirical joint distributions of the two quantities over instances in each set, and $W$ is the two-dimensional Wasserstein distance. We use a distance between distributions because we are asking whether the population of trade-offs is reproduced, not whether individual instances are copied.

Research Program

The first stage is measurement. We will take real target distributions from Distributional MIPLIB, including its real domains, optimal transmission switching and seismic-resilient pipe network planning. We will add the nurse-scheduling instances that G2MILP used from MIPLIB 2017, and the Set Covering, Combinatorial Auction and Maximum Independent Set collections used by ACM-MILP as controls. For each target, we seed four generators with a small real subset: random constraint perturbation, G2MILP across several masking ratios, ACM-MILP, and MILP-StuDio. That yields a few dozen (generator, setting, domain) configurations. For each configuration we compute two numbers: the solve-time relative error that the generator papers report, and $D_{\text{resp}}$. Measuring response at the root node keeps this cheap. We will confirm on a subset that root-node response tracks the full-solve curve of time against $\theta$.

The second stage is transfer. For each configuration we train a cut-selection policy on the synthetic set alone and evaluate it on held-out real instances. The policy is a tripartite-graph imitation learner of the lookahead expert, following Learning to Cut by Looking Ahead. We choose it because it is cheaper and more reproducible than MIRACLE's adversarial-imitation plus reinforcement-learning pipeline. A reduced MIRACLE-style run on two domains checks that conclusions do not depend on the learner. The key analysis is a rank correlation across configurations between each fidelity measure and the transfer loss. Transfer loss is the difference in primal-dual integral on real test instances between the synthetic-trained policy and a policy trained on the same number of real instances.

The third stage is constructive and deliberately simple. We filter each generator's output, keeping only candidate instances whose individual response profile lies within the real distribution's support, and we retrain. On top of this we measure a substitutability curve, following the protocol of On the Equivalency, Substitutability, and Flexibility of Synthetic Data. That paper found a 30:1 synthetic-to-real frame ratio and 60–80% replacement without loss for tracking. We will measure the corresponding ratio and replacement fraction for cut policies, with and without response filtering. No such numbers exist for integer programming; we found no reported result on Lacuna for a synthetic-to-real exchange rate in learned cut selection.

The fourth stage extends the measurement to decomposition. Here we use MILP-StuDio-style block-structured instances and a Dantzig-Wolfe solve. The knob is how many cuts are added to the master problem, and the overhead is pricing-subproblem time. This stage runs only if stage two shows the effect in the monolithic setting, since decomposition solves are far more expensive. Its purpose is to ask whether block-preserving generation also preserves how coupling cuts spill into subproblem cost. MILP-StuDio never evaluates this, because it reassembles blocks into monolithic instances.

Baselines

The naive reference point is default SCIP cut selection, run with the same time limit and hardware as every learned policy. All learned-policy results are reported relative to it. For this baseline on MIPLIB 2017, the strongest non-learned competitor is the context-aware selector of Turner, Berthold and Besançon. It reuses solver-internal scores, filters dense cuts and caps added nonzeros. It reports a solve-time ratio of 0.95 and a node ratio of 0.92 against SCIP 8.0.3, and solves 14 more instances. It matters especially here because it needs no training data at all, so it is the bar any data-dependent policy must clear on real instances. We run it on the identical real test splits.

The strongest learned reference is MIRACLE, which reports an average 3.78× speedup on MIPLIB. Its training and evaluation setup differs from ours, so we will not compare against that number directly. Instead we rerun a reduced version under our splits and the same wall-clock training budget as our imitation learner. We also cite the Distributional MIPLIB finding that on the easy optimal transmission switching tier, a learned branching policy worsened the primal-dual integral from 20.0 under SCIP to 27.9. This is a reminder that learned components can lose outright on real domains.

For generator fidelity, the strongest existing method is ACM-MILP. It reports 0.4% solve-time relative error on Set Covering, against 6.0% for G2MILP and 14.5% for random modification, and 11.1% against 43.9% node error on Maximum Independent Set. We use ACM-MILP unfiltered, with its published hyperparameters, as the main synthetic source. The upper-bound reference is a policy trained on the same number of real instances.

The ablation that isolates our key ingredient replaces response filtering with filtering on static matrix statistics: density, degree distribution and coefficient ranges. It keeps an equal number of instances and uses an equal generation budget. It asks whether dynamic cut response carries information beyond what the constraint matrix shows directly.

Beating the field means three things. Response-filtered synthetic training must close at least half of the transfer loss between unfiltered ACM-MILP data and real-data training. It must match or beat the context-aware selector's primal-dual integral on the real domains. And $D_{\text{resp}}$ must predict transfer loss with a clearly higher rank correlation than solve-time error, with bootstrap intervals over configurations that do not overlap.

Why not just…?

Why not just trust solve-time fidelity, since ACM-MILP already achieves 0.4% error? Solve time under default settings is a single point on the response curve. A cut policy is trained on the curve's shape, so it is plausible that the two decouple. This is a hypothesis, not a known result, and stage two tests it directly. If solve-time error correlates with transfer loss as well as $D_{\text{resp}}$ does, the core claim fails and we will report that. The existing generator literature would then be vindicated for this use case.

Why not just use a data-free heuristic like the context-aware selector and skip synthetic data entirely? This is a real threat. It already posts gains on MIPLIB 2017 without any inference overhead, and Distributional MIPLIB shows learned components can make real-domain performance worse. If filtered-synthetic policies cannot beat it on optimal transmission switching and pipe network planning, the practical conclusion is that synthetic training does not pay for cut selection in those domains. We would report that honestly. The measurement stage would still stand, since it explains why generators mislead.

Why not just match cheap static statistics such as density and degree instead of running cut rounds? Static density is exactly what Turner et al.'s 40% filter targets, so it may capture much of clogging cost. The static-statistics filter ablation settles this at equal budget. If it matches response filtering, we will adopt it as the recommended practice, because it is far cheaper. The contribution would then shrink to the measurement result and the exchange-rate numbers.

Why not just fine-tune on a few real instances after synthetic pre-training? Chang et al. found this works in vision. We include it as a condition in the substitutability curve rather than as a competitor. The question is whether response filtering reduces how much real data is needed for fine-tuning.

Decisive Checks

The first check is whether solve-time fidelity and response fidelity actually disagree on standard generators. We look for configurations with small solve-time error but large $D_{\text{resp}}$, particularly G2MILP at high masking ratios and random perturbation. If they never disagree, the project reduces to confirming existing metrics. The second check is the correlation comparison with transfer loss across roughly thirty configurations, with bootstrap intervals. The third check is whether response filtering beats static-statistics filtering and unfiltered ACM-MILP on held-out real instances, measured by primal-dual integral, solved count and peak memory. The fourth is the exchange-rate curve on nurse scheduling, where only two real instances exist, which tests the regime that motivates synthetic data in the first place.

As a secondary check, we compute response profiles for synthetic Packing and Max-Cut. Tang et al. (Reinforcement Learning for Integer Programming: Learning to Cut) report that a policy trained on Packing transfers to Max-Cut. NeuralCut reports the opposite. We will see whether the overlap between these two domains' response distributions is consistent with the conflicting transfer claims. This is only a hypothesis-generating test, because the two papers also differ in policy architecture.