On Learning Paradigms for the Travelling Salesman Problem

Abstract

We explore the impact of learning paradigms on training deep neural networks for the Travelling Salesman Problem. We design controlled experiments to train supervised learning (SL) and reinforcement learning (RL) models on fixed graph sizes up to 100 nodes, and evaluate them on variable sized graphs up to 500 nodes. Beyond not needing labelled data, our results reveal favorable properties of RL over SL: RL training leads to better emergent generalization to variable graph sizes and is a key component for learning scale-invariant solvers for novel combinatorial problems.

arXiv commentPresented at the NeurIPS 2019 Graph Representation Learning Workshop

References in corpus (5)

• Inductive Representation Learning on Large Graphs
• Learning Combinatorial Optimization Algorithms over Graphs
• Neural Combinatorial Optimization with Reinforcement Learning
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Attention, Learn to Solve Routing Problems!

Cited by in corpus (7)

• Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization
• Predicting Drivers' Route Trajectories in Last-Mile Delivery Using A Pair-wise Attention-based Pointer Neural Network
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
• It's Not What Machines Can Learn, It's What We Cannot Teach
• Generalization in Deep RL for TSP Problems via Equivariance and Local Search
• Maximizing Influence with Graph Neural Networks