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.

Chaitanya Joshi

Research Assistant

Chaitanya Joshi is a Research Assistant under Dr. Xavier Bresson at NTU, Singapore, applying Graph Neural Networks to Operations Research and Combinatorial Optimization.