Enhancing Branch and Bound Based Solvers through Probability Estimation via Neural Network
This paper highlights the potential of using machine learning (ML) techniques to enhance classical combinatorial optimization (CO) algorithms, particularly in the context of the Traveling Salesman Problem (TSP). The authors focus on utilizing a Graph Convolutional Network (GCN), which takes a complete graph as input and outputs a probability distribution for each edge, indicating its likelihood of being part of an optimal TSP tour. To compare the performance of the traditional branch and bound (BB) algorithm with the neural version, the authors implemented a modified version of the 1-tree branch and bound algorithm. The results demonstrate that the Graph Convolutional Branch and Bound consistently outperforms the classic BB, with the performance gap widening as the size of the instance graph increases.
Area: CS51 - Optimality: theoretical and applied results (Cristina Zucca)
Keywords: TravelingSalesmanProblem, TSP, BranchAndBound, GraphNeuralNetwork, NeuralNetworks, Optimization
Please Login in order to download this file