Learning the travelling salesperson problem requires rethinking generalization
From MaRDI portal
Publication:2152276
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.
Recommendations
- Deep policy dynamic programming for vehicle routing problems
- Learning heuristics for the TSP by policy gradient
- Solving the traveling salesperson problem with precedence constraints by deep reinforcement learning
- Machine learning for combinatorial optimization: a methodological tour d'horizon
- Generalization of machine learning for problem reduction: a case study on travelling salesman problems
Cites work
- Learning heuristics for the TSP by policy gradient
- Machine learning for combinatorial optimization: a methodological tour d'horizon
- SeaPearl: a constraint programming solver guided by reinforcement learning
- Simple statistical gradient-following algorithms for connectionist reinforcement learning
- Some Simple Applications of the Travelling Salesman Problem
- The traveling salesman problem. A computational study.
Cited in
(18)- Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem
- Learning heuristics for the TSP by policy gradient
- Deep policy dynamic programming for vehicle routing problems
- Generalization of machine learning for problem reduction: a case study on travelling salesman problems
- Dynamic graph conv-LSTM model with dynamic positional encoding for the large-scale traveling salesman problem
- Solving the traveling salesperson problem with precedence constraints by deep reinforcement learning
- Machine learning augmented approaches for hub location problems
- A differentiable approach to the maximum independent set problem using dataless neural networks
- NeuroPrim: an attention-based model for solving NP-hard spanning tree problems
- A unified pre-training and adaptation framework for combinatorial optimization on graphs
- Learn to solve dominating set problem with GNN and reinforcement learning
- An adaptive K-means and reinforcement learning (RL) algorithm to effective vaccine distribution
- Neural combinatorial optimization: a tutorial
- A machine-learning-based column generation heuristic for electric bus scheduling
- Learning and fine-tuning a generic value-selection heuristic inside a constraint programming solver
- Learning-based TSP-solvers tend to be overly greedy
- TermiNet: a reinforcement learning framework for k-path partitioning problem
- Graph convolutional branch and bound
Describes a project that uses
Uses Software
This page was built for publication: Learning the travelling salesperson problem requires rethinking generalization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2152276)
