Research map / Learning theory and algorithms / Combinatorial and search optimization
Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
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 VP-OR, a two-stage reoptimization framework that uses a GNN on historical branch-and-bound records to predict variable ranges for modified MILPs, then applies Thompson Sampling to choose which variables to fix, yielding better feasible solutions under 10-second limits.
Problem
Quickly finding high-quality feasible solutions for modified MILP instances in dynamic systems, where re-solving from scratch is too slow under strict time limits and prior reoptimization methods are limited for general MILP.
Approach
Combines GNN prediction of binary marginals and integer/continuous bounds, using features from the historical instance's final leaf-node LP basis and duals, with an online contextual Thompson Sampling bandit (Beta priors) that iteratively selects which predicted variables to fix based on whether solutions improve.
Key results
- VP-OR found feasible solutions on all 9 datasets within 10 s (5/5 each), while SCIP, ND, PS and Re Tuning failed on several (e.g., SCIP 0/5 on bnd 2 and bnd 3).
- VP-OR had the best relative gap and wins on all datasets; e.g., bnd 2 relative gap 0.11 with 5/5 wins and rhs 1 gap_rel 0.00 with 5/5 wins versus Re Tuning 0.02 and 0/5.
- Fixing 70% of variables (all types) cut solve time to under 1 s on several series (e.g., mat s1 0.37 s versus SCIP 541.78 s).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use VP-OR instead of Re Tuning | MILP reoptimization · bnd 1 | gap rel: 0.12 -> 0.02 | Helped |
| Use VP-OR instead of SCIP | MILP reoptimization · mat 1 | gap rel: 0.23 -> 0.16 | Helped |
| Use VP-OR instead of Re Tuning | MILP reoptimization · obj 2 | gap rel: 0.09 -> 0.00 | Helped |
| Use VP-OR instead of Re Tuning | MILP reoptimization · rhs 1 | gap rel: 0.02 -> 0.00 | Helped |
| Use VP-OR within a 10-second limit | MILP reoptimization · all nine datasets | solved problems within 10s | Helped |
Surprising findings
- Fixing only binary variables while adding predicted integer/continuous bounds gave 3-10x speedups, and reusing historical solver information improved binary prediction over vanilla bipartite-graph features.
- ND failed to find feasible solutions on most datasets within 10 s, suggesting end-to-end binary-only fixing is fragile for reoptimization.
Limitations
- Method may get stuck at suboptimal solutions over longer horizons (SCIP sometimes better at 100 s).
- Assumes variables are independent in the bandit model; scalability to ultra-large problems not established.
- Evaluated on only nine series of 5 test instances each, with small test sets.
Experimental setup
Datasets: MIP Computational Competition 2023 reoptimization datasets (bnd 1-3, mat 1, obj 1-2, rhs 1-3) MIPLIB 2017-derived instances IS and CA generated with Gasse et al. code (appendix)
Benchmarks: MIP Workshop 2023 reoptimization datasets (bnd 1, bnd 2, bnd 3, mat 1, obj 1, obj 2, rhs 1, rhs 2, rhs 3)
Metrics: solve number within 10s absolute primal gap relative primal gap wins
Baselines: SCIP 8.0.4 Re Tuning Neural Diving Predict-and-Search
Builds on: Neural Diving Predict-and-Search Re Tuning reoptimization Thompson Sampling
Closest papers by meaning
- ACM-MILP: Adaptive Constraint Modification via Grouping and Selection for Hardness-Preserving MILP Instance Generation (ICML 2024 · similarity 0.86)
- Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction (AAAI 2025 · similarity 0.85)
- MILP-StuDio: MILP Instance Generation via Block Structure Decomposition (NeurIPS 2024 · similarity 0.85)
- Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming (AAAI 2024 · similarity 0.84)
- Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming (ICLR 2025 · similarity 0.84)
- Contrastive Predict-and-Search for Mixed Integer Linear Programs (ICML 2024 · similarity 0.83)
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.