Lifelong Learning for Neural powered Mixed Integer Programming

Sahil Manchanda, Sayan Ranu

Introduction

Mixed Integer Programming (MIP) serves as the mathematical foundation for critical industrial optimization tasks, ranging from logistics and flight scheduling to power grid management. Most modern solvers utilize a Branch-and-Bound (B&B) algorithm, where the efficiency of the search depends heavily on the "branching" policy—the heuristic used to decide which variable to split next. While "strong branching" provides high-quality decisions, its computational cost is prohibitive. Recently, machine learning models, particularly Graph Convolutional Neural Networks (GCNNs), have been employed to approximate these expert heuristics at a fraction of the cost.

However, a significant gap exists between static research benchmarks and real-world applications. In practice, optimization problems arrive in a continuous stream, with underlying distributions shifting over time. Standard neural solvers suffer from catastrophic forgetting in these dynamic environments: as they learn to solve new problem types, their performance on previously mastered tasks degrades significantly. This paper introduces LIMIP (Lifelong Learning to Branch on Mixed Integer Programs), a framework designed to learn continually without losing past expertise.

Methodology: The LIMIP Framework

LIMIP addresses the limitations of static neural solvers through three primary technical innovations centered on problem representation and knowledge retention.

1. Edge-Weighted Bipartite Graph Attention Networks

To capture the complex structure of a MIP instance, LIMIP models the problem as a bipartite graph where one set of nodes represents variables and the other represents constraints. Unlike standard GCNNs, LIMIP utilizes an Edge-Weighted Bipartite Graph Attention Network (GAT). This architecture allows the model to explicitly "pay attention" to the specific coefficients within the constraint matrix, leading to a richer and more stable embedding of the problem state compared to previous methods.

The LIMIP architecture uses edge-weighted bipartite GAT convolutions to generate variable scores from a MIP instance.

2. Knowledge Distillation (KD)

To mitigate forgetting, LIMIP maintains a small "logit reservoir" containing samples from previous tasks. During the training of a new task, the model is optimized using a distillation loss. This penalizes the model if its predictions for historical samples drift too far from the outputs of the "expert" version of the model that was previously specialized for those tasks.

3. Elastic Weight Consolidation (EWC)

Complementing the KD approach, LIMIP employs Elastic Weight Consolidation. This technique identifies the specific neural network weights that are most critical for solving past tasks. When updating the model on new data, these important weights are "stiffened," ensuring that the model adapts to new distributions primarily through its less critical parameters.

Experimental Evaluation

The researchers evaluated LIMIP against state-of-the-art GCNN baselines across three classic NP-hard problem classes, modified to simulate drifting distributions:

  • Set Cover: Varied by changing the density of the set-item relationships.
  • Maximum Independent Set (MIS): Generated on Barabási-Albert graphs with varying sizes and affinities.
  • Facility Location: Simulated with shifting capacities and customer demands.

Key Results and Performance

Experimental results demonstrate that LIMIP significantly outperforms standard fine-tuning and other continual learning baselines.

  • Efficiency Gains: LIMIP achieved up to a 50% reduction in solving time compared to existing baselines when faced with a sequence of diverse tasks.
  • Resistance to Forgetting: While standard GCNNs saw solving times for early tasks spike as new tasks were introduced, LIMIP maintained near-constant, high-speed performance across the entire sequence.
  • Search Tree Optimization: In transfer learning scenarios, LIMIP demonstrated superior search efficiency, reducing the number of nodes in the B&B search tree for Set Cover problems from 607 (standard model) to 441.
Performance comparison between LiMIP and standard GCNN baselines across sequential tasks, showing LiMIP's stability and lower solving times.

Conclusion and Future Work

LIMIP represents a significant step toward making neural-powered MIP solvers viable for real-world, dynamic industrial environments. By combining bipartite graph attention with robust lifelong learning techniques, the framework achieves high-speed optimization without the penalty of catastrophic forgetting.

Future research directions include expanding the lifelong learning scope beyond branching to other B&B decisions, such as node selection and cutting plane application. Additionally, optimizing the model for CPU-based solvers and refining reservoir buffer management remain key challenges for further improving the scalability of lifelong learning in mathematical optimization.

Summary updated

BibTeX
@inproceedings{manchanda2023lifelong,
  author = {Sahil Manchanda and Sayan Ranu},
  title = {{Lifelong Learning for Neural powered Mixed Integer Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i7.26086},
}
Figure