Learning the travelling salesperson problem requires rethinking generalization (2020-06-12T00:00:00.000000Z)

TL;DR

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.

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.

Authors

Quentin Cappart

2 papers

T. Laurent

4 papers

Chaitanya K. Joshi

4 papers

TL;DR

Abstract

Authors

References81 items

NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem

Graph Neural Network Guided Local Search for the Traveling Salesperson Problem

Generalization in Deep RL for TSP Problems via Equivariance and Local Search

Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer

Efficient Active Search for Combinatorial Optimization Problems

A graph placement methodology for fast chip design

Neural algorithmic reasoning

Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges

Deep Policy Dynamic Programming for Vehicle Routing Problems

Combinatorial optimization and reasoning with graph neural networks

SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning

Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances

POMO: Policy Optimization with Multiple Optima for Reinforcement Learning

How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks

Learning TSP Requires Rethinking Generalization

Principal Neighbourhood Aggregation for Graph Nets

Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning

Generalization and Representational Limits of Graph Neural Networks

Improved protein structure prediction using potentials from deep learning

Learning Improvement Heuristics for Solving Routing Problems

Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning

Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer

Neural Execution of Graph Algorithms

On Learning Paradigms for the Travelling Salesman Problem

How to Evaluate Machine Learning Approaches for Combinatorial Optimization: Application to the Travelling Salesman Problem

GDP: Generalized Device Placement for Dataflow Graphs

Transferability of Spectral Graph Convolutional Neural Networks

MIPaaL: Mixed Integer Program as a Layer

A Two-Step Graph Convolutional Decoder for Molecule Generation

An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem

Exact Combinatorial Optimization with Graph Convolutional Neural Networks

What Can Neural Networks Reason About?

REGAL: Transfer Learning For Fast Optimization of Computation Graphs

Approximation Ratios of Graph Neural Networks for Combinatorial Problems

The Curious Case of Neural Text Degeneration

Coloring Big Graphs with AlphaGoZero

Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon

Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search

Learning scheduling algorithms for data processing clusters

How Powerful are Graph Neural Networks?

Learning to Perform Local Rewriting for Combinatorial Optimization

Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization

Improving Optimization Bounds using Machine Learning: Decision Diagrams meet Deep Reinforcement Learning

Learning Heuristics for the TSP by Policy Gradient

Hierarchical Graph Representation Learning with Differentiable Pooling

Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation

Relational inductive biases, deep learning, and graph networks

Attention, Learn to Solve Routing Problems!

Junction Tree Variational Autoencoder for Molecular Graph Generation

Reinforcement Learning for Solving the Vehicle Routing Problem

Learning a SAT Solver from Single-Bit Supervision

An Experimental Study of Neural Networks for Variable Graphs

Graph Attention Networks

Proximal Policy Optimization Algorithms

A Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks

Device Placement Optimization with Reinforcement Learning

Attention is All you Need

Learning Combinatorial Optimization Algorithms over Graphs

Neural Message Passing for Quantum Chemistry

In Defense of the Triplet Loss for Person Re-Identification

Neural Combinatorial Optimization with Reinforcement Learning

Divide and Conquer Networks

Understanding deep learning requires rethinking generalization

Automatic Chemical Design Using a Data-Driven Continuous Representation of Molecules

Semi-Supervised Classification with Graph Convolutional Networks

Layer Normalization

TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems

Pointer Networks

Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift

Sequence to Sequence Learning with Neural Networks

Et al

The Traveling Salesman Problem: A Computational Study

A Learning Algorithm for Continually Running Fully Recurrent Neural Networks

Some Simple Applications of the Travelling Salesman Problem

Benchmarking Graph Neural Networks

Learning Local Search Heuristics for Boolean Satisfiability