One-sentence Summary

Researchers from MIT and Microsoft Research propose a foundation model approach for $\text{Mixed Integer Linear Programming}$Mixed Integer Linear Programming ($\text{MILP}$MILP) by introducing $\text{MILP-Evolve}$MILP-Evolve, an $\text{LLM}$LLM-based evolutionary framework that generates diverse MILP classes and instances, and demonstrate significant generalization improvements on unseen problems—including $\text{MIPLIB}$MIPLIB benchmarks—across integrality gap prediction, learning to branch, and natural language alignment tasks.

Key Contributions

• The paper introduces MILP-Evolve, a large language model based evolutionary framework that generates a broad set of diverse MILP problem classes with an unlimited number of instances, directly addressing the diversity and volume limitations of existing MILP datasets.
• This work takes a foundation model training approach for MILP, training a single deep learning model on a diverse collection of MILP problems to generalize across unseen problem classes, a departure from prior methods that build class-specific models.
• The methodology is validated on three learning tasks, integrality gap prediction, learning to branch, and aligning MILP instances with natural language descriptions, and results show significant improvements on unseen problems, including MIPLIB benchmarks.

Introduction

Mixed Integer Linear Programming (MILP) is a fundamental optimization framework used across healthcare, supply chain, energy, and finance. However, MILP faces two major limitations: solving problems is computationally intensive due to NP-hardness, and understanding the formulations requires deep expertise, limiting accessibility. Researchers have tried applying machine learning to accelerate solvers, but these models are typically trained on specific problem classes, like Set Cover or Facility Location, and fail to generalize to unseen or more complex MILP formulations. This lack of generalization, combined with the scarcity of diverse, large-scale MILP training data, stands in sharp contrast to fields like computer vision and NLP, where foundation models trained on vast datasets can adapt broadly. To address these challenges, the authors propose the first foundation model training approach for MILP. They introduce MILP-Evolve, a scalable data generation pipeline that leverages Large Language Models to create over a thousand diverse MILP problem classes from few seed examples, and they train a single Graph Neural Network jointly across this broad range of classes. Their framework is evaluated on three tasks: integrality gap prediction, learning to branch, and a new MILP-to-text alignment task for interpretability. Results show substantial gains over prior work, including a 5.8x correlation improvement for integrality gap prediction and a 1.42x improvement in solved-to-optimum rate for learning to branch, while demonstrating that training data diversity matters more than data quantity alone.

Dataset

Dataset Composition and Sources

• The dataset is a collection of MILP problem classes, each represented as a modularized optimization code script. Every script contains three core functions:

  • Data: generates the coefficients for objectives and constraints, often from uniform distributions or common graph structures.
  • Optimization Modeling: defines decision variables, constraints, and the objective function.
  • Parameters: specifies problem-specific parameters such as node counts or graph density.

• The authors begin with a curated set of 8 seed MILP classes drawn from prior literature. These seeds serve as the starting point for generating a much larger and more diverse set of problem classes.

MILP-Evolve Generated Classes

• Using GPT-4o as the LLM, the authors apply a pipeline called MILP-Evolve to generate new classes through iterative transformations. The pipeline applies 10 chain-of-thought prompt operators at each iteration, randomly selecting a subset and invoking them sequentially on the previously evolved class.
• The prompt operators cover actions such as:
  • Adding or deleting constraints, variables, or associated data.
  • Crossing over two classes.
  • Mutating constraints and/or objectives.
  • Creating entirely new classes.
• Each prompt operator follows a three-module structure: (1) summarize the given MILP class, (2) describe how to modify it based on the operator type, and (3) generate the new class following the representation standard.
• To boost diversity and realism, the LLM is guided to embed the MILP problems in real-world contexts, for example, "pharmaceutical company planning cross-country vaccine distribution with storage, transport, and demand constraints." The authors also prompt the LLM to use advanced formulation techniques such as Big M, Special Order Sets, and Symmetry Breaking, making the generated instances technically challenging.

Filtering and Quality Control

• After each generation round, the authors apply a filtering step to ensure the generated classes are mathematically feasible and practically useful. The modular representation makes it easy to identify and adjust key parameters to achieve desired properties, including feasibility, appropriate solve times, and reasonable problem sizes.

How the Data Is Used

• The generated classes are added to the MILP-Evolve dataset, which is intended to support a foundation model approach for MILP. The diversity of the dataset is a central design goal, going beyond the narrow set of classes typical in prior studies.
• The paper reports that the resulting dataset is significantly more diverse than those used in earlier work. The text does not specify a training split or mixture ratio for the generated classes; the focus is on the generation pipeline and the filtering process that prepares the classes for downstream use.

Method

The authors propose a comprehensive framework that integrates a data synthesis pipeline with a multi-task learning architecture to enhance Mixed Integer Linear Programming (MILP) solvers. Refer to the framework diagram

The system is divided into two primary components: the MILP-Evolve pipeline for generating diverse training data and a learning architecture designed for specific optimization tasks.

MILP-Evolve: LLM-Based Data Synthesis To address the lack of diversity in existing MILP datasets, the authors introduce MILP-Evolve, an evolutionary pipeline that leverages Large Language Models (LLMs) to generate new problem classes. The process begins with a curated set of seed classes, typically represented as modularized optimization code scripts containing data generation, optimization modeling, and parameter definitions.

The evolution process utilizes a set of chain-of-thought prompt operators applied sequentially to the seed classes. These operators include adding constraints or variables, mutating objectives, crossing over different classes, and creating entirely new topics. To ensure realism, the LLM is prompted to integrate real-world contexts and advanced formulation techniques. As shown in the figure below:

This figure illustrates an evolution chain where an initial combinatorial auction problem is modified by adding constraints and then crossed over with a facility allocation problem to create a new, more complex instance.

Following generation, a rigorous filtering process ensures the mathematical feasibility and utility of the instances. This involves a syntax filter to check code correctness, a parameter search module to adjust problem properties like density and size, and a solution filter to verify that instances can be solved within reasonable timeframes.

Learning Architecture and Tasks The generated MILP instances serve as input for a neural network designed to learn from the data. Each MILP instance is represented as a bipartite graph connecting variable nodes and constraint nodes.

The architecture employs a Graph Convolutional Network (GCN) to embed these nodes, capturing local structural patterns. To handle global dependencies, an attention mechanism is applied over a sub-sampled set of nodes, including aggregated embeddings and a summary node. This GCN-attention structure is used for the Integrality Gap Prediction task and the MILP encoder in the Language-MILP Contrastive Learning task. For the latter, the MILP embeddings are aligned with text embeddings generated by the NV-Embed-v1 model using a symmetric cross-entropy loss, similar to the CLIP framework.

For the Learning to Branch task, the architecture is simplified to reduce computational overhead during inference. The model directly utilizes the variable embeddings produced by the GCN to predict the optimal branching variable at each node of the Branch-and-Bound tree, minimizing the cross-entropy loss against the expert strong branching actions.

Experiment

The experiments evaluate three learning tasks (integrality gap prediction, learning to branch, and contrastive language alignment) in out-of-domain settings, where a single model is trained on diverse MILP classes generated by MILP-Evolve and tested on both held-out MILP-Evolve classes and MIPLIB via transfer learning. Models trained on MILP-Evolve consistently outperform baselines using fewer or augmented classes, and the attention mechanism significantly boosts performance, while scaling the number of training classes matters far more than increasing instances. On MIPLIB, pretraining with MILP-Evolve leads to faster convergence and better fine-tuning results compared to training from scratch or with instance augmentation methods. Learning to branch remains the most challenging task, particularly in multi-class settings, and was omitted on MIPLIB due to too few solvable instances.

The proposed method consistently outperforms all baseline approaches across the three learning tasks on the held-out MILP-Evolve test set. Class diversity in training data is shown to be more critical than instance count, and the attention mechanism contributes substantially to performance gains. The learning-to-branch task remains the most challenging in this multi-class setting. The method achieves superior performance over all baselines, including seed-based and data-augmentation variants. Removing the attention mechanism leads to a clear drop in performance, highlighting its importance. Scaling training class diversity matters more than increasing instance count for generalization. The learning-to-branch task remains difficult across diverse MILP classes, suggesting future work.

On a MILP-Evolve test set derived from six unseen seed classes, initializing with the proposed pre-trained model yields the best transfer learning performance across all evaluated tasks. The model consistently outperforms training from scratch and other baselines, particularly in reducing integrality gap and improving branch prediction accuracy. The proposed pre-training method achieves the lowest integrality gap and highest correlation on the unseen test set. It also attains the best accuracy on branching predictions across multiple metrics, including top-5 and 10-way accuracy. The results highlight the importance of diverse pre-training classes for effective generalization to new problem distributions.

On the MIPLIB transfer learning benchmark, initializing with the proposed pre-trained model yields the best performance across both gap prediction and contrastive learning tasks. Pretraining on a diverse dataset consistently outperforms training from scratch, and instance augmentation methods provide only limited gains compared to the proposed approach. The proposed pre-trained model achieves the lowest deviation in integrality gap prediction and the highest correlations and accuracies in contrastive learning. Pretraining from a diverse dataset improves transfer performance over training from scratch. Instance augmentation baselines such as VAE and parameter search offer incremental improvements but remain inferior to the proposed method.

The proposed method consistently outperforms all baselines across multiple MILP benchmarks, with pre-training on diverse classes proving more critical than instance count or augmentation. The attention mechanism is essential, as its removal causes a clear performance drop, while learning-to-branch remains the most challenging task across varied MILP classes.