Research map / Learning theory and algorithms / Combinatorial and search optimization
Multi-Stage Predict+Optimize 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.
Proposes Multi-Stage Predict+Optimize, where unknown parameters are revealed over sequential stages with re-predictions, and trains NNs for MILPs via a baseline single-NN method and sequential/parallel coordinate descent over per-stage NNs.
Problem
Predict+Optimize when unknown parameters (in objectives and constraints) are revealed progressively across multiple stages with decisions made in between, so predictions should be updated stage by stage.
Approach
Extends the two-stage post-hoc regret framework to T stages where each stage re-predicts remaining parameters and hard-commits decisions; trains one NN per stage using sequential or parallel coordinate descent to handle inter-stage dependencies, with convex relaxations for gradients through MILPs.
Key results
- On the production and sales problem with 4 stages (low-profit), SCD achieved regret 293.78 vs BAS 355.56.
- On the nurse rostering problem (extra nurse payment 15), SCD achieved 607.66 vs BAS 662.34; SCD beat BAS in at least 86.67% win rate in most scenarios.
- On the investment problem with capital 50, SCD achieved 3846.20 regret at 12 stages vs BAS 3999.70; proposed methods outperform BAS in over 96.67% of simulations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use sequential coordinate descent rather than standard regression (BAS) | Multi-Stage Predict+Optimize · Production and sales, all reported price groups and stage counts | post-hoc regret | Helped |
| Use parallel coordinate descent rather than standard regression (BAS) | Multi-Stage Predict+Optimize · Production and sales | post-hoc regret | Helped |
| Train one predictor per stage with sequential coordinate descent instead of reusing one predictor | Multi-Stage Predict+Optimize · Production and sales | post-hoc regret | Helped |
| Train one predictor per stage with parallel coordinate descent instead of reusing one predictor | Multi-Stage Predict+Optimize · Investment, capital=50 | post-hoc regret | Helped |
| Use sequential coordinate descent rather than standard regression (BAS) | Multi-Stage Predict+Optimize · Nurse rostering | post-hoc regret | Helped |
| Use parallel coordinate descent rather than standard regression (BAS) | Multi-Stage Predict+Optimize · Investment problem | post-hoc regret | Helped |
| Use parallel coordinate descent instead of sequential coordinate descent | Multi-Stage Predict+Optimize · All three benchmarks | post-hoc regret | Hurt |
| Use parallel coordinate descent instead of sequential coordinate descent | Multi-Stage Predict+Optimize · Training runtime | training time | Helped |
Surprising findings
- For MILPs (investment, nurse rostering) the advantage over classical methods decreases as the number of stages grows, unlike for the LP benchmark.
- Including revealed parameters as NN inputs did not improve prediction quality while increasing training time (Appendix H.1).
Limitations
- Gradients computed through convex relaxations of MILPs rather than exact MILP formulations, introducing approximation.
- Advantage over classical methods decreases with number of stages on MILP benchmarks.
- Assumes Stage t optimization problems are always feasible (recourse assumed).
Experimental setup
Datasets: knapsack benchmark (CombOptNet) ICON scheduling competition data Ardjmand et al. generated costs and prices
Benchmarks: production and sales problem (LP) investment problem (MILP) nurse rostering problem (MILP)
Metrics: mean post-hoc regret win rate training time
Baselines: Ridge k-NN CART random forest neural network regression BAS (best standard regression) Two-Stage Baseline
Builds on: Two-Stage Predict+Optimize Mandi and Guns convex relaxation post-hoc regret
Closest papers by meaning
- Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming (ICLR 2025 · similarity 0.87)
- Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming (NeurIPS 2025 · similarity 0.86)
- Learning Generalized Linear Programming Value Functions (NeurIPS 2024 · similarity 0.86)
- Predicting Lagrangian Multipliers for Mixed Integer Linear Programs (ICML 2024 · similarity 0.86)
- Principled Data Augmentation for Learning to Solve Quadratic Programming Problems (NeurIPS 2025 · similarity 0.85)
- BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks (NeurIPS 2025 · similarity 0.85)
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.