Research map / Learning theory and algorithms / Combinatorial and search optimization
Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction
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.
Learns a preference-ranked, attention-based mapping from MILP instances to pruned model-reduction strategies (tight constraints plus integer assignments), with SetCover pruning, achieving fast and accurate MILP solving versus Gurobi and MLOPT.
Problem
Solving large-scale parameterized MILPs quickly and accurately; existing ML approaches either predict full solutions (poor scalability) or classify a single optimal reduced model, ignoring the relative performance of other feasible reduced models.
Approach
Treats the performance (objective suboptimality and constraint infeasibility) of each reduced-model strategy on each instance as a preference, learns a reward model with a pairwise/adjacent-ranking preference loss plus reward-difference MSE over attention-encoded instance-strategy pairs, and prunes labels via a SetCover greedy algorithm over an instance-strategy bipartite graph.
Key results
- On the Fuel Cell problem at the most complex setting, the method improves accuracy by nearly 39% over MLOPT (as stated in the text).
- Compared with the reward-fitting variant on Fuel Cell with k=1, the preference objective improves accuracy by about 9% on average (e.g., 95.65% vs 91.07% at T=10).
- Compared with Gurobi, the paper reports two to four orders of magnitude speedup in solving time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use preference-based learning instead of direct reward fitting (ablation) | Model reduction strategy learning · Fuel Cell Energy Management, T=10 to T=60 | accuracy: 95.65% vs 91.07%; 83.04% vs 72.43%; 73.88% vs 64.51%; 73.21% vs 63.62%; 56.14% vs 41.85%; 39.71% vs 32.90% | Helped |
| Use ranked preference samples rather than no-ranking preference pairs (ablation) | Model reduction strategy learning · Fuel Cell Energy Management, T=10 to T=60 | accuracy: 95.65% vs 89.84%; 83.04% vs 74.55%; 73.88% vs 67.19%; 73.21% vs 63.73%; 56.14% vs 50.89%; 39.71% vs 25.91% | Helped |
Surprising findings
- Reward fitting still outperforms MLOPT on the Fuel Cell problem, suggesting reward-based strategy evaluation is useful even without ranking loss.
Limitations
- Accuracy drops substantially as problem size grows (e.g., 39.71% at T=60 on Fuel Cell), and the Inventory accuracy is stated only around 90%.
- Dataset 3 is proprietary and only a de-identified LP relaxation sample is provided, limiting reproducibility.
- Experiments use a Top-k candidate scheme; the method relies on evaluating k candidate strategies online.
Experimental setup
Datasets: MIPLIB six scenarios Fuel Cell Energy Management problem (generated) Inventory Management problem (industrial, anonymized)
Benchmarks: MIPLIB six scenarios Fuel Cell Energy Management problem Inventory Management problem
Metrics: accuracy infeasibility suboptimality computation time
Baselines: Gurobi Gurobi Heuristic MLOPT Predict and Search Reward Fitting
Builds on: MLOPT Predict and Search
Closest papers by meaning
- Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming (ICLR 2025 · similarity 0.90)
- Towards Foundation Models for Mixed Integer Linear Programming (ICLR 2025 · similarity 0.89)
- Contrastive Predict-and-Search for Mixed Integer Linear Programs (ICML 2024 · similarity 0.89)
- MILP-StuDio: MILP Instance Generation via Block Structure Decomposition (NeurIPS 2024 · similarity 0.87)
- ACM-MILP: Adaptive Constraint Modification via Grouping and Selection for Hardness-Preserving MILP Instance Generation (ICML 2024 · similarity 0.87)
- RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domains (NeurIPS 2025 · similarity 0.87)
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.