Learning to Compare Nodes in Branch and Bound with Graph Neural Networks
This work addresses a key bottleneck in optimization solvers for NP-hard problems, offering incremental improvements over existing machine learning approaches.
The paper tackled the problem of node comparison in branch-and-bound for integer programming by proposing a siamese graph neural network model, resulting in faster solving times and smaller trees than default methods on NP-hard benchmarks.
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.