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.
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.
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