论文标题
学会比较分支中的节点并与图神经网络绑定
Learning to Compare Nodes in Branch and Bound with Graph Neural Networks
论文作者
论文摘要
整数编程中的分支机构方法需要订购空间的部分才能探索接下来，这个问题称为节点比较。我们提出了一个新的暹罗图神经网络模型来解决此问题，其中节点表示为具有属性的两部分图。与先前的工作类似，我们训练我们的模型，以模仿朝向最佳解决方案的潜水甲骨文。我们通过在节点根据其等级探索节点探索的纯框架中求解实例来评估我们的方法。在选择特别缺乏原始的三个NP硬质基准上，我们的方法可与开源求解器SCIP的默认排名函数以及竞争性的机器学习方法相比，可以更快地解决和较小的分支树木。此外，这些结果推广到比培训大于培训的实例。可以在https://github.com/ds4dm/learn2comparenodes上找到用于复制实验的代码。
Branch-and-bound approaches in integer programming require ordering portions of the space to explore next, a problem known as node comparison. We propose a new siamese graph neural network model to tackle this problem, where the nodes are represented as bipartite graphs with attributes. Similar to prior work, we train our model to imitate a diving oracle that plunges towards the optimal solution. We evaluate our method by solving the instances in a plain framework where the nodes are explored according to their rank. On three NP-hard benchmarks chosen to be particularly primal-difficult, our approach leads to faster solving and smaller branch- and-bound trees than the default ranking function of the open-source solver SCIP, as well as competing machine learning methods. Moreover, these results generalize to instances larger than used for training. Code for reproducing the experiments can be found at https://github.com/ds4dm/learn2comparenodes.
