论文标题
神经动力混合整数编程的终身学习
Lifelong Learning for Neural powered Mixed Integer Programming
论文作者
论文摘要
混合整数程序（MIPS）通常通过分支结合算法解决。最近，学会模仿专家强的分支启发式的快速近似，由于它成功地减少了解决MIP的运行时间，因此引起了人们的关注。但是，现有的学习与分支方法假设整个培训数据都可以在一次培训中获得。这个假设通常不是正确的，如果随着时间的流逝以连续的方式提供培训数据，那么现有的技术会遭受灾难性遗忘。在这项工作中，我们研究了迄今未开发的终身学习范式，以分支混合整数计划。为了减轻灾难性的遗忘，我们提出了Limip，该limip是由以两部分图的形式对MIP实例进行建模的想法，我们使用两部分图形注意力网络将其映射到嵌入式空间。这种丰富的嵌入空间避免了通过应用知识蒸馏和弹性重量巩固的灾难性遗忘，其中我们学习参数的关键是保持疗效，因此受到保护，免受明显的漂移。我们评估了一系列NP硬质问题的利润，并确定与现有基线相比，面对终身学习时，Limip高达50％。
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.
