Graph Neural Networks for the Travelling Salesman Problem


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.

Oct 22, 2019 12:00 AM
INFORMS Annual Meeting 2019 (Host: Quentin Cappart)
Seattle, USA
Chaitanya K. Joshi
Chaitanya K. Joshi
Research Engineer