Research map / Learning theory and algorithms / Combinatorial and search optimization
Contrastive Predict-and-Search 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 ConPaS, which trains a GCN to predict MILP solutions with a supervised contrastive loss over positive (optimal/near-optimal) and negative (infeasible or low-quality) solutions, then searches with Predict-and-Search.
Problem
Learning to predict high-quality partial solutions for MILPs so that a downstream search finds good primal solutions quickly; prior methods (Neural Diving, Predict-and-Search) use only positive samples and binary cross-entropy.
Approach
Use contrastive learning with negative samples collected by novel methods (random perturbation for infeasible solutions; local-branching-style maximin optimization for low-quality solutions), and a quality-weighted InfoNCE loss, to train the variable-score predictor used in Predict-and-Search.
Key results
- At 1,000 s, ConPaS-Inf achieves 3.54%-52.83% lower average primal gap and ConPaS-LQ 9.82%-86.02% lower than the best baseline across four benchmarks.
- On large CA instances, ConPaS-LQ's primal integral at 1,000 s is 57.9%-70.3% lower than the best baseline PaS.
- ConPaS-LQ with quality-weighted loss improves CA primal gap from 0.57% (unweighted) to 0.16% at 1,000 s in the ablation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ConPaS-LQ instead of the best baseline | MILP solution search · MVC, MIS, CA, and IP | primal integral | Helped |
| Use ConPaS-LQ instead of the best baseline | MILP solution search · MVC (large) and CA (large) | primal integral: 57.9%-70.3% lower | Helped |
| Use ConPaS-LQ instead of ConPaS-Inf | ConPaS · MVC, MIS, CA, and IP | primal gap: ConPaS-Inf achieves 3.54%-52.83% lower average primal gaps; ConPaS-LQ achieves 9.82%-86.02% lower average primal gaps th | Helped |
| Use quality-weighted InfoNCE instead of unweighted InfoNCE (ablation) | ConPaS-LQ · MVC | primal gap: 0.12% -> 0.10% | Helped |
| Use quality-weighted InfoNCE instead of unweighted InfoNCE (ablation) | ConPaS-LQ · CA | primal gap: 0.57% -> 0.16% | Helped |
| Use quality-weighted InfoNCE instead of unweighted InfoNCE (ablation) | ConPaS-LQ · MVC | primal integral: 3.3 -> 2.9 | Helped |
| Use quality-weighted InfoNCE instead of unweighted InfoNCE (ablation) | ConPaS-LQ · CA | primal integral: 24.3 -> 19.7 | Helped |
| Set k0 to 2,000 rather than 800, 1,200, 1,600, 2,400, 2,700, or 3,000 (ablation) | PaS and ConPaS-LQ · CA | primal gap: PaS: 6.28, 5.45, 2.91, 1.17, 2.19, 5.63, 12.74; ConPaS-LQ: 6.59, 5.05, 2.06, 0.55, 1.40, 4.58, 11.56 | Mixed |
Surprising findings
- Neural Diving has the lowest survival rate on CA instances, even lower than SCIP.
- ConPaS has lower classification accuracy than PaS on MVC (76.9% vs 81.2%) yet better search performance, so accuracy/AUROC does not indicate downstream quality.
Limitations
- Solutions from predicted partial assignments do not guarantee completeness or optimality.
- Neural Diving was reimplemented because its code was not available; separate model needed per benchmark problem.
Experimental setup
Datasets: Barabasi-Albert random graphs (MVC, MIS) Combinatorial auction instances (Leyton-Brown et al.) NeurIPS ML4CO item placement instances
Benchmarks: MVC MIS CA IP large MVC large CA workload appointment
Metrics: primal gap primal integral survival rate classification accuracy AUROC
Baselines: SCIP Neural Diving Predict-and-Search Gurobi
Builds on: Predict-and-Search Neural Diving InfoNCE Local Branching CL-LNS
Closest papers by meaning
- Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction (AAAI 2025 · similarity 0.89)
- Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming (ICLR 2025 · similarity 0.88)
- Towards Foundation Models for Mixed Integer Linear Programming (ICLR 2025 · similarity 0.88)
- RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domains (NeurIPS 2025 · similarity 0.87)
- Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming (NeurIPS 2025 · similarity 0.86)
- CAMBranch: Contrastive Learning with Augmented MILPs for Branching (ICLR 2024 · 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.