Attention, Learn to Solve Routing Problems!

By Wouter Kool, Herke Van Hoof, Max Welling. International Conference on Learning Representations, 2018

1,660 citations recorded by the source corpus.

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.

Subfields: Automotive Engineering, Industrial and Manufacturing Engineering, Transportation

View Paper: https://www.semanticscholar.org/paper/ce4f001c1d8ddb9a95cf54e14240ef02c44bd329

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Automotive Engineering

In Industrial and Manufacturing Engineering

In Transportation

Citations in the corpus

Combinatorial optimization and reasoning with graph neural networks (2021, methodology): “Notably, the encoder-decoder model of [Kool et al. , 2019] is adjusted for each type of problem to accommodate its special characteristics, e.g., node penalties and capacities, the constraint that a feasible tour must include all nodes or the lack thereof, et cetera.”
Model-based reinforcement learning for biological sequence design (2020, neutral): “lems (Bello et al., 2016; Bengio et al., 2018; Dai et al., 2017; Kool et al., 2018).”
POMO: Policy Optimization with Multiple Optima for Reinforcement Learning (2020, methodology): “Attention Model has been applied to routing problems including TSP, orienteering (OP), and VRP. Peng et al. [22] show that a dynamic use of Attention Model can enhance its performance.”
Rapid Task-Solving in Novel Environments (2020, background): “Especially relevant to our work is Kool et al. (2018), who show that transformers can learn to solve large combinatorial optimization problems, comparing favorably with more resource-intensive industrial solvers.”
Benchmarking Graph Neural Networks (2023, background): “Recently proposed deep learning-based solvers for COPs (Khalil et al., 2017; Li et al., 2018; Kool et al., 2019) combine GNNs with classical graph search to predict approximate solutions directly from problem instances (represented as graphs).”
Deep Reinforcement Learning for Multiobjective Optimization (2019, methodology): “For example, the MOTSP can be solved by integrating any of the recently proposed novel DRL-based TSP solvers [17], [21] into the DRL-MOA framework.”
Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning (2021, methodology): “Although RL methods only utilizes the transition samples during learning, they can successfully solve various CO problems without employing pre-computed optimal solutions [27, 21, 19].”
Transformers without Tears: Improving the Normalization of Self-Attention (2019, neutral): “Both have been applied to self-attention [1, 21].”
Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning (2020, background): “travelling salesman problem) [12, 13, 14, 15, 16, 17], graph optimization problems [18, 19], and the satisfiability problem (SAT) [20, 21, 22].”
Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model (2024, methodology): “2) heuristics designed automatically: The attention model (AM) (Kool et al., 2018) is the seminal work on adopting neural networks to learn the heuristics for solving combinatorial optimization problems.”
DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization (2023, methodology): “We use the same test instances as [54, 64] for TSP-50/100 and [27] for TSP-500/1000/10000.”
An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem (2019, methodology): “TSP20 Model [Kool et al., 2019] 3 .”
Learning to Perform Local Rewriting for Combinatorial Optimization (2018, methodology): “[35] and AM [29]) over the test set of: (a) expression simplification; (b) job scheduling; (c) vehicle routing.”
Differentiation of Blackbox Combinatorial Solvers (2019, background): “Some works have again targeted the TRAVELING-SALESMAN-PROBLEM [6, 9, 25] as well as other NP-Hard problems [27].”
Large Language Models as Optimizers (2023, background): “…including heuristic algorithms and solvers (Rosenkrantz et al., 1977; Golden et al., 1980; Optimization et al., 2020; Applegate et al., 2006; Helsgaun, 2017), and approaches based on training deep neural networks (Kool et al., 2019; Deudon et al., 2018; Chen & Tian, 2019; Nazari et al., 2018).”
Solving Mixed Integer Programs Using Neural Networks (2020, methodology): “More recently, deep learning has been applied to the Travelling Salesman Problem (Vinyals et al. 2015, Bello et al. 2016), Vehicle Routing (Kool et al. 2019, Nazari et al. 2018), Boolean Satisfiability (Selsam et al. 2019), and general graph-structured combinatorial optimization problems (Khalil et ”