LIMIP: Lifelong Learning to Solve Mixed Integer Programs
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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Hybrid Models for Learning to Branch cites Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies
- Lifelong Learning with Behavior Consolidation for Vehicle Routing cites Dark Experience for General Continual Learning: a Strong, Simple Baseline
Cited by top-tier papers2
Builds on7
- Dark Experience for General Continual Learning: a Strong, Simple BaselinePietro Buzzega, Matteo Boschini, Angelo Porrello, Davide Abati et al.NeurIPS 2020 · 1,494 citations
- Hybrid Models for Learning to BranchPrateek Gupta, Maxime Gasse, Elias B. Khalil, Pawan Kumar Mudigonda et al.NeurIPS 2020 · 179 citations
- Overcoming Catastrophic Forgetting in Graph Neural Networks with Experience ReplayFan Zhou, Chengtai CaoAAAI 2021 · 175 citations
- Overcoming Catastrophic Forgetting in Graph Neural NetworksHuihui Liu, Yiding Yang, Xinchao WangAAAI 2021 · 166 citations
- Parameterizing Branch-and-Bound Search Trees to Learn Branching PoliciesGiulia Zarpellon, Jason Jo, Andrea Lodi, Yoshua BengioAAAI 2021 · 123 citations
Related papers
- BTBS-LNS: Binarized-Tightening, Branch and Search on Learning LNS Policies for MIPHao Yuan, Wenli Ouyang, Changwen Zhang, Yong Sun et al.ICLR 2025
- L2P-MIP: Learning to Presolve for Mixed Integer ProgrammingChang Liu, Zhichen Dong, Haobo Ma, Weilin Luo et al.ICLR 2024 · 10 citations
- Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution PredictionJian-Ya Ding, Chao Zhang, Lei Shen, Shengyin Li et al.AAAI 2020 · 119 citations
- A General Neural Backbone for Mixed-Integer Linear Optimization via Dual AttentionPeixin Huang, Yaoxin Wu, Yining Ma, Cathy Wu et al.ICML 2026
- Reinforcement Learning for Branch-and-Bound Optimisation Using Retrospective TrajectoriesChristopher W. F. Parsonson, Alexandre Laterre, Thomas D. BarrettAAAI 2023 · 30 citations
