Neural Combinatorial Optimization with Reinforcement Learning

By Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, Samy Bengio. 2016

1,854 citations recorded by the source corpus.

This paper presents a framework to tackle combinatorial optimization problems using neural networks and reinforcement learning. We focus on the traveling salesman problem (TSP) and train a recurrent network that, given a set of city coordinates, predicts a distribution over different city permutations. Using negative tour length as the reward signal, we optimize the parameters of the recurrent network using a policy gradient method. We compare learning the network parameters on a set of training graphs against learning them on individual test graphs. Despite the computational expense, without much engineering and heuristic designing, Neural Combinatorial Optimization achieves close to optimal results on 2D Euclidean graphs with up to 100 nodes. Applied to the KnapSack, another NP-hard problem, the same method obtains optimal solutions for instances with up to 200 items.

Subfields: Artificial Intelligence, Reinforcement Learning

How researchers see this paper

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

In Artificial Intelligence

In Reinforcement Learning

Citations in the corpus

Attention Augmented Convolutional Networks (2019, background): “Attention has enjoyed widespread adoption as a computational module for modeling sequences because of its ability to capture long distance interactions [2, 44, 4, 3].”
Seq2SQL: Generating Structured Queries from Natural Language using Reinforcement Learning (2017, methodology): “, 2016], combinatorial optimization [Bello et al., 2017], and question answering [Seo et al.”
Efficient Neural Architecture Search via Parameter Sharing (2018, background): “0 for the sampling logits (Bello et al., 2017a;b), and add the controller’s sample entropy to the reward, weighted by 0 .”
Learning Combinatorial Optimization Algorithms over Graphs (2017, methodology): “This contrasts with recent approaches [37, 6] that adopt a graph-agnostic sequence-to-sequence mapping that does not fully exploit graph structure.”
Relational inductive biases, deep learning, and graph networks (2018, background): “Many traditional computer science problems, which involve reasoning about discrete entities and structure, have also been explored with graph neural networks, such as combinatorial optimization (Bello et al., 2016; Nowak et al., 2017; Dai et al., 2017), boolean satisfiability (Selsam et al.”
Relational Deep Reinforcement Learning (2018, background): “This approach builds off previous work suggesting that relational computations needn’t necessarily be biased by entities’ spatial proximity [20, 10, 21, 11, 13], and may also profit from iterative structured reasoning [22, 23, 24, 25].”
Boosting the Actor with Dual Critic (2017, background): “Actor-critic methods combine the beneﬁts of these two classes, and have proved successful in a number of challenging problems such as robotics (Deisenroth et al., 2013), meta-learning (Bello et al., 2016), and games (Mnih et al., 2016).”
LambdaNetworks: Modeling Long-Range Interactions Without Attention (2021, background): “12Sometimes the attention operation is instead used to point to specific context elements (Vinyals et al., 2015; Bello et al., 2016), which is not supported by lambda layers.”
Fast Abstractive Summarization with Reinforce-Selected Sentence Rewriting (2018, methodology): “Our extractor combines reinforcement learning and pointer networks, which is inspired by Bello et al. (2017)’s attempt to solve the Traveling Salesman Problem.”
Learning a SAT Solver from Single-Bit Supervision (2018, background): “…showing that various neural network architectures can learn good heuristics for NP -hard combinatorial optimization problems (Vinyals et al., 2015; Bello et al., 2016; Dai et al., 2017); however, ﬁnding low-cost solutions to optimization problems requires less precise reasoning than ﬁnding…”
Causal Discovery with Reinforcement Learning (2019, methodology): “Besides [1], there are many other successful RL applications in recent years, e.g., AlphaGo [23], where the typical goal is to learn a good policy.”
Neural Program Synthesis with Priority Queue Training (2018, methodology): “…adopted in this paper for program synthesis is closely related to neural architecture search (Zoph & Le, 2017) and neural combinatorial optimization (Bello et al., 2016), where variants of PG are used to train an RNN and a pointer network (Vinyals et al., 2015) to perform combinatorial search.”
Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing (2018, background): “These assumptions characterize the problem of program synthesis well, but also apply to many structured prediction problems [47, 37] and combinatorial optimization domains ( e.g. , [7]).”
An Introduction to Deep Reinforcement Learning (2018, positive): “Finally, it should be mentioned that deep RL has applications in classic and fundamental algorithmic problems in the field of computer science, such as the travelling salesman problem (Bello et al., 2016).”
Learning Decision Trees with Reinforcement Learning (2017, background): “This framework has obtained promising solutions on a variety of problems, like neural architecture search [18], neural optimizer search [3], combinatorial optimization [2] and device placement [10].”
Device Placement Optimization with Reinforcement Learning (2017, background): “Our work is closely related to the idea of using neural networks and reinforcement learning for combinatorial optimization (Vinyals et al., 2015; Bello et al., 2016).”
Attention, Learn to Solve Routing Problems! (2018, positive): “2016) (also when using an LSTM based critic), but our reproduction is closer than others have reported (Dai et al., 2017; Nazari et al., 2018).”