LIMIP: Lifelong Learning to Solve Mixed Integer Programs
DOI:
https://doi.org/10.1609/aaai.v37i7.26086Keywords:
ML: Graph-based Machine Learning, ML: ApplicationsAbstract
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 learningDownloads
Published
2023-06-26
How to Cite
Manchanda, S., & Ranu, S. (2023). LIMIP: Lifelong Learning to Solve Mixed Integer Programs. Proceedings of the AAAI Conference on Artificial Intelligence, 37(7), 9047-9054. https://doi.org/10.1609/aaai.v37i7.26086
Issue
Section
AAAI Technical Track on Machine Learning II