Graph Convolutional Neural Networks for the Travelling Salesman Problem
Abstract
Combinatorial optimization problems, also called NP-hard problems, are practical constraint satisfaction problems that are impossible to solve optimally at large scales. In practice, handcrafted heuristic algorithms are able to solve problems with up to a million variables and constraints. These algorithms are the backbone of modern industries such as transportation, supply chain, and scheduling. However, coming up with good heuristics requires significant specialized knowledge. A recent line of work investigates using deep neural networks to directly learn these heuristics from problem instances instead. In this paper, we introduce a novel deep learning approach for approximately solving the most famous NP-hard problem in recent history, the Travelling Salesman Problem. We focus on the 2D Euclidean TSP and use Graph Convolutional Neural Networks and beam search to predict a valid TSP tour given an input graph with up to 100 nodes. Our approach outperforms all recently proposed deep learning techniques in terms of both solution quality and speed when evaluated on problem instances of fixed graph sizes. However, experiments on the generalization capabilities of our models show a drastic drop in performance when evaluated on graph sizes different from those that models were trained on. Our results highlight an important flaw in the current paradigm of learningbased approaches for TSP and combinatorial optimization: comparing among approaches based on performance for discrete problem sizes completely ignores generalization. We advocate for the machine learning community to switch focus towards building size-agnostic models with strong generalization capabilities in order to scale up to realistic problem sizes.
