LIMIP: Lifelong Learning to Solve Mixed Integer Programs

Sahil Manchanda, Sayan Ranu

Introduction

Mixed Integer Programming (MIP) serves as the mathematical foundation for critical industrial applications, including logistics, scheduling, and resource allocation. Solving these NP-hard problems typically involves the Branch-and-Bound (B&B) algorithm, where "strong branching"—the process of selecting the next variable to split—is a computationally intensive bottleneck. While recent "learning to branch" (L2B) approaches use neural networks to approximate these heuristics, they are generally trained on static datasets. In dynamic real-world environments where problem distributions drift, these models suffer from catastrophic forgetting, losing efficiency on older problem types as they adapt to new ones. LIMIP introduces the first lifelong learning framework designed to address this challenge.

Methodology: Bipartite GAT and Knowledge Retention

LIMIP (Lifelong Learning to Solve Mixed Integer Programs) reimagines the L2B pipeline through two primary innovations: state encoding and sequential learning strategies.

State Encoding with Bipartite GAT

MIP instances are naturally represented as bipartite graphs, with nodes for variables and constraints. Unlike traditional Graph Convolutional Neural Networks (GCNNs), LIMIP utilizes an edge-weighted bipartite Graph Attention Network (GAT). This architecture allows the model to learn more nuanced representations by dynamically weighting the importance of neighboring nodes, such as the specific influence of a constraint on a variable's embedding.

The LIMIP architecture uses a bipartite Graph Attention Network (GAT) to generate variable scores from MIP instances.

Mitigating Catastrophic Forgetting

To enable continuous learning without performance degradation on prior tasks, LIMIP employs a dual-loss strategy:

  • Knowledge Distillation (KD): The model maintains a "logit reservoir" of samples from previous tasks. During new training phases, it attempts to match its current outputs to the logits previously produced for these samples, preserving past behavior.
  • Elastic Weight Consolidation (EWC): This technique identifies parameters critical to past tasks and penalizes significant changes to them, ensuring that the network's "memory" of earlier problem structures remains intact.

Experimental Evaluation

The framework was tested on three NP-hard problem classes with drifting distributions: Set Cover (varying set-item probabilities), Independent Set (varying graph sizes and affinities), and Facility Location (drifting capacities and demands).

Key Results

LIMIP demonstrates a significant advancement in the stability and efficiency of learned solvers:

  • Minimal Forgetting: While standard GCNN-based methods saw solving times on earlier tasks increase dramatically as new tasks were introduced, LIMIP maintained near-constant performance across the entire task sequence.
  • Solving Efficiency: In lifelong learning scenarios, LIMIP outperformed baselines by up to 50% in solving time.
  • Superior Branching: The model consistently produced smaller B&B trees, indicating that its branching decisions more closely approximate the high-quality "expert" strong branching heuristic.
Solving time performance across sequential Set Cover tasks. LIMIP (red) demonstrates superior stability and efficiency compared to GCNN-based lifelong learning baselines.

Conclusion and Future Work

LIMIP proves that lifelong learning is viable for combinatorial optimization, allowing solvers to adapt to evolving data without losing prior expertise. Future research will focus on extending this framework to other B&B decisions, such as node selection and heuristic management, and optimizing the computational overhead associated with EWC parameter tracking.

Summary updated

Abstract

Mixed Integer programs (MIPs) are typically solved by the Branch-and-Bound algorithm. Recently, Learning to imitate fast approximations of the expert strong branching heuristic has gained attention due to its success in reducing the running time for solving MIPs. However, existing learning-to-branch methods assume that the entire training data is available in a single session of training. This assumption is often not true, and if the training data is supplied in continual fashion over time, existing techniques suffer from catastrophic forgetting. In this work, we study the hitherto unexplored paradigm of Lifelong Learning to Branch on Mixed Integer Programs. To mitigate catastrophic forgetting, we propose LIMIP, which is powered by the idea of modeling an MIP instance in the form of a bipartite graph, which we map to an embedding space using a bipartite Graph Attention Network. This rich embedding space avoids catastrophic forgetting through the application of knowledge distillation and elastic weight consolidation, wherein we learn the parameters key towards retaining efficacy and are therefore protected from significant drift. We evaluate LIMIP on a series of NP-hard problems and establish that in comparison to existing baselines, LIMIP is up to 50% better when confronted with lifelong learning
BibTeX
@inproceedings{manchanda2023limip,
  author = {Sahil Manchanda and Sayan Ranu},
  title = {{LIMIP: Lifelong Learning to Solve Mixed Integer Programs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i7.26086},
}
Figure