Learning the Travelling Salesperson Problem Requires Rethinking Generalization
Preprint
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.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Generalization in Deep RL for TSP Problems via Equivariance and Local SearchSN Computer Science, 2024
- Learning Improvement Heuristics for Solving Routing ProblemsIEEE Transactions on Neural Networks and Learning Systems, 2022
- Deep Policy Dynamic Programming for Vehicle Routing Problems2022
- SeaPearl: A Constraint Programming Solver Guided by Reinforcement Learning2021
- A graph placement methodology for fast chip designNature, 2021
- Machine learning for combinatorial optimization: A methodological tour d’horizonEuropean Journal of Operational Research, 2021
- Understanding deep learning (still) requires rethinking generalizationCommunications of the ACM, 2021
- Improved protein structure prediction using potentials from deep learningNature, 2020
- Learning Heuristics for the TSP by Policy Gradient2018
- Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning1992