Neural Combinatorial Optimization with Reinforcement Learning

2016-11-29 · Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, Samy Bengio

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.

📄 PDF Abstract BibTeX arXiv:1611.09940

Code (10)

JoseVillagranE/Pointer-Networks pytorch

Rintarooo/TSP_DRL_PointerNet pytorch

Rintarooo/TSP_DRL_PtrNet pytorch

Rintarooo/TSP_RL_Pointer_Actor_Critic pytorch

abdullah-al-masud/rl-optimize pytorch

ahottung/EAS pytorch

chaitjo/learning-tsp pytorch

longkangli/pfss-il pytorch

pemami4911/neural-combinatorial-rl-pytorch pytorch

zhengsr3/Reinforcement_Learning_Pointer_Networks_TSP_Pytorch pytorch

Tasks

Combinatorial Optimizationreinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Traveling Salesman Problem

Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch

2022-06-14 · Tianyu Zhang, Amin Banitalebi-Dehkordi, Yong Zhang

Branch-and-bound is a systematic enumerative method for combinatorial optimization, where the performance highly relies on the variable selection strategy. State-of-the-art handcrafted heuristic strategies suffer from re…

BIG-bench Machine Learning Combinatorial Optimization Deep Reinforcement Learning Imitation Learning+4

Hamiltonian-based Quantum Reinforcement Learning for Neural Combinatorial Optimization

2024-05-13 · Georg Kruse, Rodrigo Coehlo, Andreas Rosskopf, Robert Wille 외

Advancements in Quantum Computing (QC) and Neural Combinatorial Optimization (NCO) represent promising steps in tackling complex computational challenges. On the one hand, Variational Quantum Algorithms such as QAOA can …

Combinatorial Optimization reinforcement-learning Reinforcement Learning

Unraveling the Rainbow: can value-based methods schedule?

2025-05-06 · Arthur Corrêa, Alexandre Jesus, Cristóvão Silva, Samuel Moniz

Recently, deep reinforcement learning has emerged as a promising approach for solving complex combinatorial optimization problems. Broadly, deep reinforcement learning methods fall into two categories: policy-based and v…

Atari Games Combinatorial Optimization Deep Reinforcement Learning Job Shop Scheduling+3

Combinatorial Optimization Augmented Machine Learning

2026-01-15 · Maximilian Schiffer, Heiko Hoppe, Yue Su, Louis Bouvier 외 arxiv

Combinatorial optimization augmented machine learning (COAML) has recently emerged as a powerful paradigm for integrating predictive models with combinatorial decision-making. By embedding combinatorial optimization orac…

Stochastic Optimization Reinforcement Learning

Constrained Combinatorial Optimization with Reinforcement Learning

2020-06-22 · Ruben Solozabal, Josu Ceberio, Martin Takáč

This paper presents a framework to tackle constrained combinatorial optimization problems using deep Reinforcement Learning (RL). To this end, we extend the Neural Combinatorial Optimization (NCO) theory in order to deal…

Combinatorial Optimization Deep Reinforcement Learning reinforcement-learning Reinforcement Learning+1