Learning the Travelling Salesperson Problem Requires Rethinking Generalization

Abstract

End-to-end training of neural network solvers for graph combinatorial optimization problems such as the Travelling Salesperson Problem (TSP) have seen a surge of interest recently, but remain intractable and inefficient beyond graphs with few hundreds of nodes. While state-of-the-art learning-driven approaches for TSP perform closely to classical solvers when trained on trivially small sizes, they are unable to generalize the learnt policy to larger instances at practical scales. This work presents an end-to-end neural combinatorial optimization pipeline that unifies several recent papers in order to identify the inductive biases, model architectures and learning algorithms that promote generalization to instances larger than those seen in training. Our controlled experiments provide the first principled investigation into such zero-shot generalization, revealing that extrapolating beyond training data requires rethinking the neural combinatorial optimization pipeline, from network layers and learning paradigms to evaluation protocols. Additionally, we analyze recent advances in deep learning for routing problems through the lens of our pipeline and provide new directions to stimulate future research.

arXiv commentAccepted to the 27th International Conference on Principles and Practice of Constraint Programming (CP 2021) and Constraints (2022). Code and data available at https://github.com/chaitjo/learning-tsp

References in corpus (46)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Sequence to Sequence Learning with Neural Networks
• TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer
• WaveNet: A Generative Model for Raw Audio
• Language Models are Few-Shot Learners
• In Defense of the Triplet Loss for Person Re-Identification
• Understanding deep learning requires rethinking generalization
• Learning Combinatorial Optimization Algorithms over Graphs
• Junction Tree Variational Autoencoder for Molecular Graph Generation
• Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks
• Learning to Simulate Complex Physics with Graph Networks
• Gated Graph Sequence Neural Networks
• How Powerful are Graph Neural Networks?
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• Neural Combinatorial Optimization with Reinforcement Learning
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• Principal Neighbourhood Aggregation for Graph Nets
• Benchmarking Graph Neural Networks
• Device Placement Optimization with Reinforcement Learning
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Quantifying Generalization in Reinforcement Learning
• Attention, Learn to Solve Routing Problems!
• Learning a SAT Solver from Single-Bit Supervision
• Chip Placement with Deep Reinforcement Learning
• Tacotron: Towards End-to-End Speech Synthesis
• Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks
• What Can Neural Networks Reason About?
• Augmenting Genetic Algorithms with Deep Neural Networks for Exploring the Chemical Space
• A Survey of Deep Learning for Scientific Discovery
• Generalization and Representational Limits of Graph Neural Networks
• Learning Improvement Heuristics for Solving Routing Problems
• SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver
• Coloring Big Graphs with AlphaGoZero
• Encoding Sentences with Graph Convolutional Networks for Semantic Role Labeling
• GDP: Generalized Device Placement for Dataflow Graphs
• Systematic Generalization: What Is Required and Can It Be Learned?
• On Learning Paradigms for the Travelling Salesman Problem
• Transforming task representations to perform novel tasks
• How to Evaluate Machine Learning Approaches for Combinatorial Optimization: Application to the Travelling Salesman Problem
• Graph2Seq: Scalable Learning Dynamics for Graphs
• Compositional Generalization with Tree Stack Memory Units

Cited by in corpus (11)

• Graph neural network initialisation of quantum approximate optimisation
• Neural Airport Ground Handling
• Learning Collaborative Policies to Solve NP-hard Routing Problems
• ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning
• Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimization
• Size-Invariant Graph Representations for Graph Classification Extrapolations
• From Local Structures to Size Generalization in Graph Neural Networks
• It's Not What Machines Can Learn, It's What We Cannot Teach
• Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art
• A New Constructive Heuristic driven by Machine Learning for the Traveling Salesman Problem
• Experiments with graph convolutional networks for solving the vertex $p$-center problem