Research map / Learning theory and algorithms / Combinatorial and search optimization
Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming
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.
Apollo-MILP alternates GNN-based prediction of partial MILP solutions with a trust-region solver correction, and fixes only variables where predicted and reference solutions agree (UEBO-based consistency criterion), reducing the solution gap by over 50% on CA, SC, IP, WA benchmarks.
Problem
Neural MILP solution prediction methods (Neural Diving, Predict-and-Search) fix predicted variable values, which can yield low-quality or infeasible reduced problems when predictions are inaccurate.
Approach
Use the solver's trust-region search output as a reference solution to correct the GNN prediction, then fix only variables where prediction and reference agree, justified by an uncertainty-based error upper bound (UEBO) on KL divergence.
Key results
- On CA, Apollo-MILP with Gurobi reduces absolute primal gap from 319.07 (Gurobi) to 129.41 and PS+Gurobi's 258.36, a 52.2% improvement over Gurobi; on SC gap 0.10 vs 0.45 for Gurobi.
- On IP and WA, Ours+Gurobi reaches the best-known values (8.90 and 704.88) within 1,000s, beating single-thread Gurobi at 3,600s.
- On the IIS MIPLIB subset with 3,600s limit, Ours achieves objective 209.33 versus 211.00 for PS and 214.00 for Gurobi.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Apollo-MILP instead of ConPS with Gurobi | Gurobi solving on CA · CA test | absolute primal gap: 152.49 -> 129.41 | Helped |
| use Apollo-MILP instead of ConPS with Gurobi | Gurobi solving on SC · SC test | absolute primal gap: 0.25 -> 0.10 | Helped |
| use Apollo-MILP instead of ConPS with Gurobi | Gurobi solving on IP · IP test | absolute primal gap: 0.19 -> 0.00 | Helped |
| use Apollo-MILP instead of ConPS with Gurobi | Gurobi solving on WA · WA test | absolute primal gap: 0.49 -> 0.00 | Helped |
| use Apollo-MILP instead of ConPS with SCIP | SCIP solving on CA · CA test | absolute primal gap: 792.33 -> 777.25 | Helped |
| use Apollo-MILP instead of ConPS with SCIP | SCIP solving on SC · SC test | absolute primal gap: 0.95 -> 0.55 | Helped |
| use Apollo-MILP instead of ConPS with SCIP | SCIP solving on IP · IP test | absolute primal gap: 4.84 -> 3.96 | Helped |
| use Apollo-MILP instead of ConPS with SCIP | SCIP solving on WA · WA test | absolute primal gap: 4.45 -> 4.41 | Helped |
| replace consistency-based fixing with direct fixing of reference partial solutions (ablation) | Apollo-MILP on IP · IP test | absolute primal gap: 0.00 -> 0.32 | Hurt |
| replace consistency-based fixing with direct fixing of reference partial solutions (ablation) | Apollo-MILP on WA · WA test | absolute primal gap: 0.00 -> 0.52 | Hurt |
| replace consistency-based fixing with four rounds of PS fixing predicted partial solutions (ablation) | Apollo-MILP on IP · IP test | absolute primal gap: 0.00 -> 0.28 | Hurt |
| replace consistency-based fixing with four rounds of PS fixing predicted partial solutions (ablation) | Apollo-MILP on WA · WA test | absolute primal gap: 0.00 -> 0.45 | Hurt |
Surprising findings
- Neural Diving performs worse than plain Gurobi on the IP and WA benchmarks in some settings, e.g. ND+Gurobi gap 1613.59 on CA versus 319.07 for Gurobi.
- On IP and WA, the method's 1,000s runtime outperforms Gurobi's 3,600s runtime, with BKS redefined from the method's own results.
Limitations
- Relies on BKS defined partly by the method's own results for IP and WA, which may bias gap measurements.
- Performance sensitive to hyperparameters (k0, k1, delta) that require tuning; ND/ConPS baselines have no public code and were reproduced by the authors.
Experimental setup
Datasets: Combinatorial auctions (CA) Set covering (SC) NeurIPS ML4CO 2021 item placement (IP) NeurIPS ML4CO 2021 workload appointment (WA)
Benchmarks: CA SC IP WA IIS (MIPLIB subset)
Metrics: best objective absolute primal gap relative primal gap
Baselines: Gurobi SCIP Neural Diving Predict-and-Search ConPS Warm-starting Gurobi
Builds on: Predict-and-Search Neural Diving ConPS
Closest papers by meaning
- Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction (AAAI 2025 · similarity 0.90)
- Towards Foundation Models for Mixed Integer Linear Programming (ICLR 2025 · similarity 0.89)
- RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domains (NeurIPS 2025 · similarity 0.89)
- Contrastive Predict-and-Search for Mixed Integer Linear Programs (ICML 2024 · similarity 0.88)
- Predicting Lagrangian Multipliers for Mixed Integer Linear Programs (ICML 2024 · similarity 0.87)
- Multi-Stage Predict+Optimize for (Mixed Integer) Linear Programs (NeurIPS 2024 · 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.