Many hard planning problems under uncertainty, such as where to open facilities before demand is known, are now solved by training a small neural network to predict the cost of what happens after the decision. That network is then written directly into an integer program, so a commercial solver can search over decisions. This avoids the "scenario explosion" of writing out every possible future. But it moves the bottleneck. Every ReLU neuron that might be either on or off becomes a yes/no variable the solver must branch on. A more accurate, larger surrogate therefore makes the optimization problem harder. Model compression should help, but the compression literature measures cost in parameters, memory and latency. Those are the wrong currencies here.
We propose to compress optimization surrogates by the quantity the solver actually pays for: the number of neurons whose on/off state is undecided over the set of allowed decisions. Neurons that are provably always on or always off on that set need no yes/no variable. Pushing neurons into those states, then repairing the resulting error with bias corrections that cost the solver nothing, should yield surrogates that are both larger and cheaper to optimize over. We judge success by the true cost and feasibility of the decisions the solver returns, not by prediction error.
Core Claim
Neur2SP trains ReLU networks to approximate the second-stage (after-uncertainty) cost of two-stage stochastic programs. It embeds them in a mixed-integer program (MIP) using big-M constraints, which encode each neuron with one binary variable and four linear inequalities. Its scenario-set model, NN-E, solves CFLP, SSLP, INVP and pooling instances in under 1.66 seconds with objective gaps under 5%, where the extensive form takes hours. The paper treats surrogate size as fixed. It also notes that loose big-M bounds and growing networks slow the solver.
Our claim has two parts. First, the binary-variable count of the embedded model is governed by unstable neurons, those whose pre-activation can take either sign as the first-stage decision $x$ ranges over its feasible set $X$. Parameter count matters much less. Standard magnitude or structured pruning, as used in Super Tickets or LLM-Streamline, targets weights and so can remove many parameters while leaving most binaries in place.
Second, the compression-accuracy trade-off in this setting should be measured in decision space. We expect a cliff that is sharper than the cliff in prediction error. A small, systematic distortion of the surrogate can move the solver's chosen $x$ to a different discrete decision, or to one with no feasible second stage.
For NN-E on a fixed instance, the scenario-set embedding is a constant. Stability can therefore be certified per instance over $X$ alone, which makes the stability count both computable and tight.
Research Program
The work builds a solver-aware compression pipeline in three steps and studies when it beats simply training a small network.
The first step is certification. For each neuron $j$ and instance, we compute bounds $[l_j, u_j]$ on its pre-activation over $X$, by interval propagation followed by LP-based bound tightening. Neurons with $l_j \ge 0$ become linear identities, and neurons with $u_j \le 0$ are deleted. The number of binaries the solver sees is the count of neurons with $l_j < 0 < u_j$. These bounds also tighten the big-M constants, which addresses the numerical weakness Neur2SP reports.
The second step is stabilization. Starting from a deliberately over-sized surrogate, we fine-tune on the original solver-labeled data plus a penalty on sampled decisions $x \in X$. The penalty pushes pre-activations away from zero. We also prune neurons that are unstable but contribute little to output variance. This follows the "train big, then compress" logic of Li et al., who found that pruned large transformers beat small ones trained from scratch at equal size. They also found the advantage vanishes at around 1% data, and that finding constrains us: solver labels are expensive, and ML-L-Shaped used up to a million solves. We therefore treat label budget as an explicit experimental axis rather than assuming abundance.
The third step is healing at zero solver cost. RestoreLCC repairs pruned language models in two moves. It decomposes the activation gap between dense and pruned models by SVD, keeping minor as well as principal directions. It then folds learned magnitudes into existing bias terms. Inside a MIP a bias is only a constant in a linear constraint, so it adds no variables. We reuse this method. On calibration decisions, we take the per-layer gap between dense and stabilized activations, keep a few SVD directions, fit scalar magnitudes, and fold them into biases.
We also test a decision-focused variant. It fits the magnitudes to reduce the true cost of decisions returned by the compressed MIP on a small set of training instances, rather than to reduce activation error. This responds directly to the "predict-and-optimize" gap that ML-L-Shaped leaves open.
A bias is a constant shift and cannot correct input-dependent errors. Healing may therefore be weak, and that is one of the things we measure.
Baselines
The naive reference point is dense Neur2SP NN-E embedded with the same tightened bounds we use, so that gains from bound tightening alone are not credited to compression. The file's reported figures for this system are solve times under 1.66 seconds and objective gaps under 5% (Neur2SP). No reported result found on Lacuna for per-instance binary-variable counts or recourse-infeasibility rates of Neur2SP, so we will measure both ourselves.
The strongest competitor on the scaling question is a small network trained from scratch to the same binary budget. It is the obvious thing a practitioner would do, and on low-label problems it may genuinely win. It gets the same labels, the same hyperparameter search budget in GPU-hours, and the same stability penalty, so that the comparison isolates "big then compress" against "small from the start."
The strongest existing exact-quality method is ML-L-Shaped. It never embeds a network in the MIP, using it instead to approximate recourse inside L-shaped decomposition. It reports a 175x speedup over exact solvers on SSLP and roughly 80% time reduction on SMKP, with optimality gaps below 0.1%. That is a far tighter gap than Neur2SP's under-5%. We run it on the shared SSLP instances with its published setup and report wall-clock including offline label generation.
Two ablations isolate our key ingredient. The first is magnitude and structured pruning at matched parameter counts, without stability awareness or healing, in the spirit of Super Tickets. The second is stability-aware compression with healing removed. Beating a baseline means a strictly better curve of true optimality gap against binary count (equivalently, MIP solve time). The comparison is made at matched label budget, and recourse-infeasibility is no higher.
Why not just…?
Why not just train a smaller surrogate? This is the real threat. Li et al.'s evidence favours compressing large models, but it comes from data-rich transformer training. Their own low-data result points the other way, and operations research labels are scarce. We do not argue around this. The label-budget sweep, from 1% to 100% of each benchmark's training set, directly settles where, if anywhere, compression dominates. If small-from-scratch with the stability penalty matches us everywhere, the contribution becomes the stability penalty and the decision-space evaluation, and we will report it that way.
Why not just prune by weight magnitude, as in LLM compression? Magnitude pruning removes weights, but a neuron with fewer weights is still a binary variable unless its sign becomes fixed over $X$. The matched-parameter ablation tests whether parameter savings translate into solver savings. Our hypothesis is that they mostly do not.
Why not avoid embedding altogether and use decomposition with learned cuts? ML-L-Shaped already achieves sub-0.1% gaps on SSLP. If it is also faster end-to-end once its million-solve data cost is counted, MIP embedding is the wrong architecture. Our comparison includes offline cost precisely to decide this. Embedding retains one advantage: a single-solve formulation that extends to settings without decomposable recourse, such as the non-convex pooling problem.
Why not just tighten big-M bounds and stop? Bound tightening alone is our naive baseline, so its contribution is measured separately from stabilization and healing.
Proposed Experiments
We use Neur2SP's CFLP, SSLP and INVP benchmarks, plus SIPLIB's SMKP instances from ML-L-Shaped. Each surrogate is evaluated by solving the embedded MIP and then fixing the returned $x$. We solve the true second stage exactly over a held-out scenario set and report the relative gap to the best known extensive-form value. Alongside the gap we report solve time, binary count, branch-and-bound nodes, and the fraction of scenarios with infeasible recourse.
The first decisive check is the Pareto curve of true gap against binary count across compression levels. If stability-aware compression with healing does not dominate magnitude pruning and small-from-scratch at matched label budgets, the core claim fails.
The second check is the shape of the cliff. We plot prediction error and decision gap against compression level on the same axis to test whether decisions collapse before regression error visibly degrades. This would show that compression must be validated in decision space.
The third check asks whether compression buys accuracy at fixed solver time. Under a fixed solve-time cap, a compressed large surrogate should reach a smaller gap than the dense surrogate that fits the cap.
A secondary probe tests the super-ticket phase transition reported for BERT: does light compression improve gaps when test instances use more scenarios than training? This is exploratory, and a null result would not affect the main claim.
References
- Neur2SP: Neural Two-Stage Stochastic Programming
- Super Tickets in Pre-Trained Language Models: From Model Compression to Improving Generalization
- Streamlining Redundant Layers to Compress Large Language Models
- Train Big, Then Compress: Rethinking Model Size for Efficient Training and Inference of Transformers
- Fast Continuous and Integer L-Shaped Heuristics Through Supervised Learning
- Restoring Pruned Large Language Models via Lost Component Compensation