Learning to Compare Nodes in Branch and Bound with Graph Neural Networks

Autor:	Labassi, Abdel Ghani, Chételat, Didier, Lodi, Andrea
Rok vydání:	2022
Předmět:	Computer Science - Machine Learning Computer Science - Artificial Intelligence
Druh dokumentu:	Working Paper
Popis:	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. Comment: 7 pages, 3 figures, 2 tables
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2210.16934 Zobrazit plný text záznamu View this record from Arxiv