Attention, Learn to Solve Routing Problems!

Abstract

The recently presented idea to learn heuristics for combinatorial optimization problems is promising as it can save costly development. However, to push this idea towards practical implementation, we need better models and better ways of training. We contribute in both directions: we propose a model based on attention layers with benefits over the Pointer Network and we show how to train this model using REINFORCE with a simple baseline based on a deterministic greedy rollout, which we find is more efficient than using a value function. We significantly improve over recent learned heuristics for the Travelling Salesman Problem (TSP), getting close to optimal results for problems up to 100 nodes. With the same hyperparameters, we learn strong heuristics for two variants of the Vehicle Routing Problem (VRP), the Orienteering Problem (OP) and (a stochastic variant of) the Prize Collecting TSP (PCTSP), outperforming a wide range of baselines and getting results close to highly optimized and specialized algorithms.

arXiv commentAccepted at ICLR 2019. 25 pages, 7 figures

Cited by in corpus (84)

• Graph Neural Networks: A Review of Methods and Applications
• Attention in Natural Language Processing
• Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning
• Benchmarking Graph Neural Networks
• Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Deep Reinforcement Learning for Electric Vehicle Routing Problem with Time Windows
• Deep Q-Learning for Same-Day Delivery with Vehicles and Drones
• Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
• Graph Neural Networks: Taxonomy, Advances and Trends
• Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learning
• Learning to Perform Local Rewriting for Combinatorial Optimization
• Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
• POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
• Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers
• Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning
• End to end learning and optimization on graphs
• Graph neural network initialisation of quantum approximate optimisation
• Learning Improvement Heuristics for Solving Routing Problems
• Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing
• Reinforcement Learning Applications
• NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem
• Learning Collaborative Policies to Solve NP-hard Routing Problems
• Solving Mixed Integer Programs Using Neural Networks
• Learn to Design the Heuristics for Vehicle Routing Problem
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization
• Learning Variable Ordering Heuristics for Solving Constraint Satisfaction Problems
• One model Packs Thousands of Items with Recurrent Conditional Query Learning
• Efficient Active Search for Combinatorial Optimization Problems
• Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer
• Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances
• On Learning Paradigms for the Travelling Salesman Problem
• Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero
• Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers
• Convolution, attention and structure embedding
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs
• Matrix Encoding Networks for Neural Combinatorial Optimization
• Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention
• Attend2Pack: Bin Packing through Deep Reinforcement Learning with Attention
• Estimating Gradients for Discrete Random Variables by Sampling without Replacement
• Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
• CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints
• A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems
• Learning to simulate and design for structural engineering
• Learning Large Neighborhood Search Policy for Integer Programming
• Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimization
• It's Not What Machines Can Learn, It's What We Cannot Teach
• Solving Continual Combinatorial Selection via Deep Reinforcement Learning
• Storchastic: A Framework for General Stochastic Automatic Differentiation
• Siamese Graph Neural Networks for Data Integration
• Graph2Seq: Scalable Learning Dynamics for Graphs
• Deep Reinforcement Learning for Multi-Driver Vehicle Dispatching and Repositioning Problem
• Ordering-Based Causal Discovery with Reinforcement Learning
• Unsupervised Community Detection with Modularity-Based Attention Model
• Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art
• Learning Practically Feasible Policies for Online 3D Bin Packing
• Topology Aware Deep Learning for Wireless Network Optimization
• Generalization in Deep RL for TSP Problems via Equivariance and Local Search
• Set-to-Sequence Methods in Machine Learning: a Review
• Few-shots Parallel Algorithm Portfolio Construction via Co-evolution
• Learning Combined Set Covering and Traveling Salesman Problem
• Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach
• Neural Execution of Graph Algorithms
• Curriculum Design for Teaching via Demonstrations: Theory and Applications
• Real-Time Neural Network Scheduling of Emergency Medical Mask Production during COVID-19
• Learning to Dynamically Coordinate Multi-Robot Teams in Graph Attention Networks
• R3L: Connecting Deep Reinforcement Learning to Recurrent Neural Networks for Image Denoising via Residual Recovery
• Adversarial Neural Trip Recommendation
• A Game-Theoretic Approach for Improving Generalization Ability of TSP Solvers
• Curriculum learning for multilevel budgeted combinatorial problems
• Learning to Delegate for Large-scale Vehicle Routing
• Supervised Off-Policy Ranking
• Adversarial Deep Learning for Online Resource Allocation
• dFDA-VeD: A Dynamic Future Demand Aware Vehicle Dispatching System
• Computing Steiner Trees using Graph Neural Networks
• Learning Combinatorial Node Labeling Algorithms
• Leveraging Recursive Gumbel-Max Trick for Approximate Inference in Combinatorial Spaces
• Fixed Priority Global Scheduling from a Deep Learning Perspective
• MODRL/D-EL: Multiobjective Deep Reinforcement Learning with Evolutionary Learning for Multiobjective Optimization
• Rapid Task-Solving in Novel Environments
• Where the Action is: Let's make Reinforcement Learning for Stochastic Dynamic Vehicle Routing Problems work!
• Experiments with graph convolutional networks for solving the vertex $p$-center problem
• Graph Convolutional Policy for Solving Tree Decomposition via Reinforcement Learning Heuristics