Graph Convolutional Branch and Bound
This work addresses efficiency in solving NP-hard problems like the Traveling Salesman Problem, offering a hybrid approach that is incremental but improves exact solvers.
The paper tackled NP-hard combinatorial optimization problems by integrating neural networks to learn heuristics for branch-and-bound algorithms, resulting in a significant reduction in explored nodes and computational time for the Traveling Salesman Problem.
This article explores the integration of deep learning models into combinatorial optimization pipelines, specifically targeting NP-hard problems. Traditional exact algorithms for such problems often rely on heuristic criteria to guide the exploration of feasible solutions. In this work, we propose using neural networks to learn informative heuristics-most notably, an optimality score that estimates a solution's proximity to the optimum. This score is used to evaluate nodes within a branch-and-bound framework, enabling a more efficient traversal of the solution space. Focusing on the Traveling Salesman Problem, we describe two exact solvers-1-tree branch-and-bound and Concorde-and introduce a hybrid approach called Graph Convolutional Branch and Bound, which augments these solvers with a graph convolutional neural network along with a novel unsupervised training strategy that facilitates generalization to graphs of varying sizes without requiring labeled data. Empirical results demonstrate the effectiveness of the proposed method, showing a significant reduction in the number of explored branch-and-bound nodes and overall computational time.