Research map / Learning theory and algorithms / Combinatorial and search optimization
Predicting Lagrangian Multipliers for Mixed Integer Linear Programs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Trains a probabilistic GNN encoder and MLP decoder to predict Lagrangian multipliers for MILPs from the continuous relaxation solution, optimizing the Lagrangian bound directly, and shows gains on Multi-Commodity Network Design and Generalized Assignment.
Problem
Lagrangian dual problems for MILPs require iterative gradient-like methods (subgradient, bundle) whose cost grows quickly with the number of relaxed constraints, so obtaining good Lagrangian multipliers is computationally expensive.
Approach
Amortize per-instance Lagrangian multiplier optimization by predicting LMs with a probabilistic GNN encoder over the factor bipartite graph (with CR primal/dual solutions as input) and an MLP decoder that outputs deviations from CR duals, trained end-to-end by maximizing the Lagrangian bound (unsupervised, no gold LMs).
Key results
- On Mc-Sml-40 the method reaches 2.09% GAP versus 12.97% for LR(CR) and 12.99% for CR, closing roughly 84% of the gap.
- On Mc-Big-Var, warm-starting the bundle solver with predicted LMs cuts time from 89.26 s (CR init) to 57.23 s at epsilon 1e-3, and iterations from 179 to 143.
- On Ga-20-400 the method reaches 0.15% GAP versus 0.27% for LR(CR), a 44% gap reduction over the second-best method.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the proposed encoder-decoder instead of LR(MLP) | Lagrangian multiplier prediction · Mc-Sml-40 test | GAP %: 10.70 -> 2.09 | Helped |
| use the proposed encoder-decoder instead of LR(MLP) | Lagrangian multiplier prediction · Mc-Sml-Var test | GAP %: 16.71 -> 4.42 | Helped |
| use the proposed encoder-decoder instead of LR(MLP) | Lagrangian multiplier prediction · Mc-Big-40 test | GAP %: 13.67 -> 4.20 | Helped |
| use the proposed encoder-decoder instead of LR(MLP) | Lagrangian multiplier prediction · Mc-Big-Var test | GAP %: 16.14 -> 4.77 | Helped |
| use the proposed encoder-decoder instead of LR(MLP) | Lagrangian multiplier prediction · Ga-10-100 test | GAP %: 0.78 -> 0.55 | Helped |
| use the proposed encoder-decoder instead of LR(CR) | Lagrangian multiplier prediction · Ga-20-400 test | GAP %: 0.27 -> 0.15 | Helped |
| add multiple LM samples and keep the best (ablation) | Ours · Mc-Sml-40 and Mc-Big-Var | GAP %: 2.10 -> 2.09; 4.79 -> 4.77 | Helped |
| predict deviations from CR dual values rather than full LMs (ablation) | Ours · Mc-Sml-40 and Mc-Big-Var | GAP %: 2.63 -> 2.09; 6.77 -> 4.77 | Helped |
| add CR solution features and CR-based LM initialization (ablation) | Ours · Mc-Sml-40 and Mc-Big-Var | GAP %: 20.26 -> 2.09; 23.78 -> 4.77 | Helped |
| use probabilistic sampling rather than a deterministic encoder (ablation) | Ours · Mc-Sml-40 and Mc-Big-Var | GAP %: 2.18 -> 2.09; 5.86 -> 4.77 | Helped |
| warm-start the Bundle solver with predicted LMs instead of zero initialization | Bundle solver on Mc-Big-Var validation · epsilon 1e-1 | time (s): 34.34 ($\pm$81.22 ) -> 16.09 ( $\pm$ 42.79 ) | Helped |
| warm-start the Bundle solver with predicted LMs instead of CR dual solutions | Bundle solver on Mc-Big-Var validation · epsilon 1e-4 | time (s): 101.14 ($\pm$283.52 ) -> 63.25 ( $\pm$ 190.47 ) | Helped |
Surprising findings
- Predicting LMs from CR input is not simply copying CR: without CR features (-cr variant), GAP reduction versus LR(0) is still around 80%, though the absolute gap is 20.26%.
- k-NN regression over LMs performs poorly, sometimes worse than CR, even on near-duplicate instances.
Limitations
- Restricted to compact MILPs and Lagrangian relaxations that give a bound tighter than CR, since CR primal and dual solutions are inputs.
- Subgradient warm-starting shows little benefit with the given step-size schedule.
- Generalization tested only from Mc-Big-Var to larger instances, with a single train-test pairing.
Experimental setup
Datasets: Canad (Multi-Commodity Network Design instances, subset) GA instances e10100 and e20400 (used for distribution parameters) synthetic MC and GA instances generated by the authors
Benchmarks: Mc-Sml-40 Mc-Sml-Var Mc-Big-40 Mc-Big-Var Ga-10-100 Ga-20-400
Metrics: GAP % time (ms) time (s) # iterations
Baselines: continuous relaxation (CR) LR(0) LR(CR) k-NN MLP SMS++ bundle method subgradient method
Builds on: Lagrangian relaxation Gasse et al. GNN MILP encoding reparameterization trick bundle method
Closest papers by meaning
- Learning Valid Dual Bounds in Constraint Programming: Boosted Lagrangian Decomposition with Self-Supervised Learning (AAAI 2025 · similarity 0.90)
- Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming (ICLR 2025 · similarity 0.87)
- Principled Data Augmentation for Learning to Solve Quadratic Programming Problems (NeurIPS 2025 · similarity 0.87)
- Towards Foundation Models for Mixed Integer Linear Programming (ICLR 2025 · similarity 0.87)
- Learning Generalized Linear Programming Value Functions (NeurIPS 2024 · similarity 0.86)
- Learn2Aggregate: Supervised Generation of Chvatal-Gomory Cuts Using Graph Neural Networks (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.