Presentation on YouTube.

The Branch and Bound method aims to find optimal solutions to NP-hard problems. It divides the search space into subproblems, which are recursively solved, while eliminating branches whose potential solution is inferior to the one already found. The choice of the exploration order of nodes is essential to the performance of this algorithm. An efficient selection strategy can speed up the solution and reduce the branching tree. We will discuss various node selection approaches, with an emphasis on data-based methods. We will also present our contribution, which uses graph neural networks to compare nodes, which are represented as bipartite graphs. Our model, capable of handling variable dimension data, has shown faster resolution and reduction of the branching tree than competitors, across three NP-hard benchmarks, while offering natural generalization to larger instances.