Research map / Learning theory and algorithms / Combinatorial and search optimization

Towards Foundation Models for Mixed Integer Linear Programming

ICLR 2025 · Learning theory and algorithms › Combinatorial and search optimization · approach: Learning branch-and-cut for MILP · 3 citations (OpenAlex)

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 MILP-Evolve, an LLM-driven evolutionary pipeline that generates over a thousand diverse MILP problem classes, and trains a GNN-with-attention foundation-style model across three MILP tasks (integrality gap prediction, learning to branch, language-MILP contrastive alignment) that generalizes to unseen classes and MIPLIB.

Problem

Existing deep learning approaches for MILP are trained on specific problem classes and fail to generalize to unseen classes, and existing MILP datasets lack diversity and volume.

Approach

Use GPT-4o in an evolutionary loop (add, crossover, mutate, new, delete prompt operators with chain-of-thought) over modular optimization code, followed by parameter grid search and filtering, to generate a large diverse set of MILP classes; then train one GCN+attention model per task on this data.

Key results

• On the MILP-Evolve held-out test set, the Ours model reaches 20.14% deviation and 0.58 correlation for integrality gap prediction versus 32.96% and 0.10 for Seed.
• For learning to branch, Ours (GCN) solves 70.90% of instances to optimality within 200s versus 49.59% for Seed (GCN), with a 15.49% time improvement over SCIP default including network overhead.
• On MIPLIB transfer for contrastive learning, Ours achieves 82.08% 4-way and 75.57% 10-way accuracy, above Seed (79.69%, 72.71%).

Measured effects reported in the paper

Surprising findings

• Diversity of training classes matters much more than the number of training instances: reducing classes at fixed instance count hurts performance, while reducing instances per class has minimal effect.
• The VAE-based instance augmentation baseline underperforms simple parameter search augmentation for contrastive learning and branching, and in IG it yields only modest gains.

Limitations

• Still trains a separate model for each learning task rather than one unified foundation model.
• Learning to branch remains challenging in the multi-class setting, with only modest gains over SCIP default when excluding overhead for some baselines.
• Learning-to-branch on MIPLIB was omitted because too few MIPLIB instances fall in a usable solve-time range.

Experimental setup

Datasets: MILP-Evolve generated classes MIPLIB Seed classes (IS, SC, CA, CF, KS, GIS, NF, SAT)

Benchmarks: MILP-Evolve held-out test set MILP-Evolve unseen seed-class test set MIPLIB

Metrics: mean absolute deviation Pearson correlation proportion solved to optimal within 200s shifted geometric mean time improvement 4-way accuracy 10-way accuracy top-5 accuracy

Baselines: Mean Seed Seed + Param. Seed + VAE GPT-4o SCIP Default

Builds on: CLIP NV-Embed-v1 strong branching GCN (Gasse et al.) VAE-based instance generation (Han et al.)

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.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)
• ACM-MILP: Adaptive Constraint Modification via Grouping and Selection for Hardness-Preserving MILP Instance Generation (ICML 2024 · similarity 0.86)