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.

Accepted 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 (20)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Sequence to Sequence Learning with Neural Networks
• WaveNet: A Generative Model for Raw Audio
• Language Models are Few-Shot Learners
• Understanding deep learning requires rethinking generalization
• Learning to Simulate Complex Physics with Graph Networks
• Neural Combinatorial Optimization with Reinforcement Learning
• Principal Neighbourhood Aggregation for Graph Nets
• Benchmarking Graph Neural Networks
• Device Placement Optimization with Reinforcement Learning
• Chip Placement with Deep Reinforcement Learning
• Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks
• A Survey of Deep Learning for Scientific Discovery
• Generalization and Representational Limits of Graph Neural Networks
• SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver
• GDP: Generalized Device Placement for Dataflow Graphs
• 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

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