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.

Date
Oct 22, 2019 12:00 AM
Location
INFORMS Annual Meeting 2019
Seattle, WA
Avatar
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.

Related