Testing the Theory of Learned Lagrangian Multipliers on Real Solvers

Many hard integer programs have a few "coupling" constraints that tie otherwise independent pieces together. Lagrangian relaxation is the classic trick for such problems: move those constraints into the objective with a price (a multiplier) on each, and the problem splits into easy subproblems whose optimal value is a lower bound on the true optimum. The quality of that bound depends entirely on the prices. Finding good prices normally takes hundreds of slow subgradient iterations per instance. A recent theory paper, Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming, proves how many training instances a model needs in order to predict good prices. It also makes sharp claims: the error should shrink as $s/\sqrt{N}$ when the model predicts prices directly, and as $s/N$ when the prediction only warm-starts a conventional solver. Here $s$ is the number of coupling constraints and $N$ the number of training instances. The paper tests none of this on data or on a real solver.

This proposal treats that paper as a set of falsifiable predictions and checks them on standard mixed-integer benchmarks, under the distribution shifts that real deployments face. The training signal needs no labels. Minimizing the Lagrangian integrality gap (the distance between the Lagrangian bound and the true optimum) is the same as maximizing the bound itself, so a model can train on raw instances without solving any of them exactly. The practical reason to care concerns speed. Neural branching policies call the network at every node of the search tree, and this can make the solver slower than default SCIP, as reported by Distributional MIPLIB. A multiplier predictor is called once per instance, before the search starts, so it should sidestep that per-node cost. That is a hypothesis we test, not a fact we assume.

Core Claim

For an integer program $\min_{x \in X} c^\top x$ subject to coupling constraints $Ax \ge b$, write the Lagrangian bound as

$$L(\pi) = \min_{x \in X} \; c^\top x + \pi^\top (b - Ax), \qquad \pi \ge 0.$$

Here $X$ is the set of solutions that satisfy only the easy, decomposable constraints, and $\pi$ is the vector of $s$ prices. The Lagrangian integrality gap is $\mathrm{OPT} - L(\pi)$, where $\mathrm{OPT}$ is the true integer optimum. Since $\mathrm{OPT}$ does not depend on $\pi$, making the gap small is exactly the same as making $L(\pi)$ large. A predictor $\pi_\theta$ (a model with weights $\theta$ that maps an instance to prices) can therefore be trained by gradient ascent on $L(\pi_\theta)$ using supergradients from the subproblem solutions, with no oracle labels.

The claim has three parts, each testable:

  1. The theory's rates show up empirically on finite samples. The fitted log-log slope of excess dual gap against $N$ should be near $-1/2$ for direct prediction and near $-1$ for warm-starting.
  2. Excess error grows roughly linearly with $s$.
  3. On instances where this relaxation beats the linear programming bound, a one-shot learned warm-start reaches a given bound quality in less wall-clock time than both default dual ascent and SCIP's own root bound, including the network's inference time.

We add a question the theory cannot answer because it assumes training and test distributions match: does the advantage survive when models trained on Easy instances are tested on Medium and Hard ones?

Relation to Prior Work

This proposal borrows its central mechanism from structured prediction.

  • The mechanism. Train and Test Tightness of LP Relaxations in Structured Prediction and its predecessor On the Tightness of LP Relaxations for Structured Prediction showed that training against a relaxed objective implicitly penalizes the integrality gap. On Yeast this yielded 99.57% integral test solutions, against 17.7% under exact training. They also proved that this tightness generalizes to new instances drawn from the same distribution.
  • How we differ. Those papers concern the scoring weights of a linear structured model over graphical-model polytopes, evaluated on small classical datasets. We apply the same "optimize the relaxed objective and the gap shrinks" logic to prices in general integer programs, where the relaxation is Lagrangian rather than a local polytope. We also test the generalization claim out of distribution, which neither paper does.
  • Theory under test. The Lagrangian relaxation paper supplies the theory we are testing. We change nothing in its analysis and add only the measurements it lacks.
  • The constraint. Distributional MIPLIB motivates the wall-clock focus. Its default SCIP reached a primal-dual integral of 20.0 on the easiest optimal transmission switching distribution, against 27.9 for the learned branching policy. The authors attribute this to neural evaluation inside the search loop.
  • The closest learned approach to gap closure. Learn2Aggregate uses a graph neural network to choose which constraints to combine into Chvátal-Gomory cuts. It closes roughly twice as much of the integrality gap as the standard method on its largest instances and runs 40% faster than the exact separator. It needs labels from an expensive exact oracle and evaluates cut rounds in isolation. Our objective is label-free, and we time our method end to end.

Research Program

Choosing relaxations that matter. The first step guards against an outcome that would make the study meaningless. If each subproblem left after relaxation is itself solvable exactly as a linear program (the "integrality property"), the best Lagrangian bound equals the plain linear programming bound. Learning prices then only buys speed over solving a linear program, which solvers already do well. We therefore choose relaxations whose subproblems lack this property, so that the best Lagrangian bound can be strictly stronger:

  • Capacitated facility location: relax the constraints that assign each customer, leaving one knapsack problem per facility.
  • Set covering: the classic Lagrangian relaxation.
  • p-median: a similar decomposition.
  • Vehicle-routing family: synthetic instances built as described in the Lagrangian relaxation paper, so that the theory's setting is reproduced exactly.

For each domain we first report how much of the gap between the linear programming bound and the optimum the best Lagrangian prices close, computed by long bundle-method runs. This tells us the headroom before any learning.

Two predictors. The first is a fixed-size model for experiments where $s$ is held constant, which matches the theory. The second is a graph neural network on the variable-constraint graph that outputs one price per constraint, so that it transfers across instance sizes. Each predictor is trained two ways:

  • Direct: maximize $L(\pi_\theta)$ itself.
  • Warm-start: maximize the bound reached after $k$ subgradient steps initialized at $\pi_\theta$, following the theory's warm-start formulation.

Rate experiments. We vary $N$ on a logarithmic grid from 10 to 5,000 instances and vary $s$ by scaling instance size. We measure excess dual gap, $\mathbb{E}[L(\pi^\star) - L(\hat\pi)]$ normalized by $|L(\pi^\star)|$, where $\pi^\star$ are the best prices. We fit slopes with bootstrap confidence intervals.

Stochastic gradient ascent versus fitting the training set. The theory separates plain empirical risk minimization, with a rate of $s^{1.5}/\sqrt{N}$, from stochastic gradient ascent with iterate averaging, with a rate of $s/\sqrt{N}$. We run both to see whether the extra $\sqrt{s}$ factor appears in practice.

Baselines

Zero prices. The naive reference point is dual ascent started from zero prices using a standard subgradient method with Polyak-style step sizes. It gets the same per-instance time limit and the same subproblem solver as our method. Every speedup is reported against it.

Linear programming duals. A stronger and cheaper reference solves the linear programming relaxation first, then starts subgradient ascent from the dual values of the relaxed coupling constraints. This is the baseline a practitioner would actually use. It already encodes each instance's structure, and its cost is a single linear program. Beating it means reaching a bound within 1% of $L(\pi^\star)$ in less total time, with linear program time counted for the baseline and network time counted for us, on the median instance.

Default SCIP root bound. SCIP's root-node bound with its default cuts is the strongest existing non-learned method. It is run single-threaded on the same hardware with its default settings. On the question of whether learning pays inside a real solver, the most relevant reported figure is Distributional MIPLIB's primal-dual integral of 20.0 for default SCIP versus 27.9 for learned branching on OTS (Easy). We found no reported result on Lacuna for learned Lagrangian multipliers on any benchmark, which is itself the gap this work fills. Beating SCIP means a stronger bound at equal wall-clock time on domains where the Lagrangian headroom is positive.

Supervised regression. This ablation isolates the label-free objective. We regress onto the best prices computed by bundle methods, with the same architecture and tuning budget. The label-generation time is reported separately as the cost the label-free objective avoids.

Nearest-neighbor reuse. A second simple competitor copies the best prices of the most similar training instance, measured by instance feature distance. This tests whether a network is needed at all.

Warm-start versus direct. The final ablation compares the two training modes. It isolates the ingredient the theory singles out as the source of the faster $s/N$ rate.

Why not just…?

Why not just use the linear programming duals and skip learning? This is the most serious threat. When the subproblems have the integrality property, the linear programming duals already give the best Lagrangian bound, and learning cannot improve the bound. That is why we restrict the headline experiments to relaxations with measured positive headroom and report that headroom first. Even then, linear programming duals may be good enough starting points that the learned warm-start adds little. The paired comparison of time to reach 1% of the best bound settles this directly. We commit to reporting a null result if the learned warm-start does not beat these duals.

Why not just reuse multipliers from similar past instances? On fixed-size, stationary distributions, nearest-neighbor reuse may match a network, and the theory's rates would apply to it too. It has no natural way to transfer across instance sizes, though, because the number of prices changes with size. The Easy-to-Hard shift experiment is where it should fail. If it does not, we will conclude that the network is unnecessary.

Why not just train on optimal multipliers as labels? Supervised regression is a legitimate alternative that works well when labels are cheap. The structured prediction results suggest that optimizing the relaxed objective itself shapes the solution in a way that imitation does not: exact training produced 17.7% integrality against 99.57% for relaxed training in On the Tightness of LP Relaxations for Structured Prediction. Regression loss also weights all price errors equally, even though the bound is insensitive to many of them. The head-to-head comparison at equal total compute, label generation included, decides this.

Why not just let SCIP do it? SCIP's cuts may close more of the gap than any Lagrangian bound on some domains. The per-domain headroom measurement and the equal-time bound comparison will show where that happens, and we will report those domains as losses rather than exclude them.

Proposed Experiments

Decisive check 1: the rates. At fixed $s$, the fitted slope of log excess gap against log $N$ should lie in $[-0.65, -0.35]$ for direct prediction and in $[-1.2, -0.8]$ for warm-starting, with non-overlapping confidence intervals between the two. If the slopes coincide, the theory's warm-start speedup does not appear on finite samples, and we will locate the cause. The main candidate is that $k$ subgradient steps are too few to reach the strongly convex regime the warm-start analysis relies on. A second check is whether excess gap scales linearly with $s$, the number of coupling constraints.

Decisive check 2: wall-clock time. On the facility location, set covering and p-median instances used by Learn2Aggregate, and on the Distributional MIPLIB domains that admit a clean decomposition, we measure median and 90th-percentile time to reach 1% of the best bound. Both baselines are included, and network inference time is counted. We also plug the bound into SCIP's root node and measure the primal-dual integral against default SCIP. This asks directly whether one-shot prediction avoids the inference bottleneck that per-node branching policies suffer.

Decisive check 3: distribution shift. Models are trained on the Easy level and tested on Medium, Hard and Very Hard. We track excess gap relative to in-distribution performance, and whether the warm-start mode degrades more gracefully than direct prediction. Because the subgradient steps after warm-starting can correct a poor starting point, the warm-start mode should degrade more gracefully. The multi-domain training setting from Distributional MIPLIB, which pools five domains at 80 instances per domain, serves as a second shift condition.

Success means that the theory's rate predictions hold, or fail in an explained way, and that the learned warm-start beats linear programming duals on time to bound in at least the domains with positive headroom. Failure on either count would be a publishable correction to a purely theoretical result, and it would still meet the file's call for empirical validation.