Graph Neural Networks for the Travelling Salesman Problem

Abstract

The most famous NP-hard combinatorial problem today, the Travelling Salesman Problem, is intractable to solve optimally at large scale. In practice, existing techniques such as Concorde can efficiently solve TSP up to thousands of nodes. This talk introduces a recent line of work from the deep learning community to directly ‘learn’ good heuristics for TSP using neural networks. Our approach uses Graph ConvNets to operate on the graph structure of problem instances and is highly parallelizable, making it a promising direction for learning combinatorial optimization at large scale.