# Reinforcement Learning for Combinatorial Optimization: A Survey

arXiv: https://arxiv.org/abs/2003.03600 · HTML: https://mlsanity.com/paper/2003.03600/

## Key facts

- Cited by 236 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Mar 2020.

## Built on by (most cited first, 30 of 236)

- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Deep Policy Dynamic Programming for Vehicle Routing Problems](https://mlsanity.com/paper/2102.11756/) (2021)
- [GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time](https://mlsanity.com/paper/2312.08224/) (2023)
- [BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization](https://mlsanity.com/paper/2301.03313/) (2023)
- [DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization](https://mlsanity.com/paper/2309.14032/) (2023)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization](https://mlsanity.com/paper/2210.03475/) (2022)
- [Pareto Set Learning for Neural Multi-objective Combinatorial Optimization](https://mlsanity.com/paper/2203.15386/) (2022)
- [RouteFinder: Towards Foundation Models for Vehicle Routing Problems](https://mlsanity.com/paper/2406.15007/) (2024)
- [Optimized Feature Generation for Tabular Data via LLMs with Decision Tree Reasoning](https://mlsanity.com/paper/2406.08527/) (2024)
- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [Constructions in combinatorics via neural networks](https://mlsanity.com/paper/2104.14516/) (2021)
- [Boost then Convolve: Gradient Boosting Meets Graph Neural Networks](https://mlsanity.com/paper/2101.08543/) (2021)
- [Combinatorial Optimization with Policy Adaptation using Latent Space Search](https://mlsanity.com/paper/2311.13569/) (2023)
- [On Representing Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2209.12288/) (2022)
- [OptiMUS: Optimization Modeling Using MIP Solvers and large language models](https://mlsanity.com/paper/2310.06116/) (2023)
- [Diffusion Models as Constrained Samplers for Optimization with Unknown Constraints](https://mlsanity.com/paper/2402.18012/) (2024)
- [ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning](https://mlsanity.com/paper/2106.03051/) (2021)
- [Challenges and Opportunities in Deep Reinforcement Learning with Graph Neural Networks: A Comprehensive review of Algorithms and Applications](https://mlsanity.com/paper/2206.07922/) (2022)
- [The Expressive Power of Graph Neural Networks: A Survey](https://mlsanity.com/paper/2308.08235/) (2023)
- [Bridging Evolutionary Algorithms and Reinforcement Learning: A Comprehensive Survey on Hybrid Algorithms](https://mlsanity.com/paper/2401.11963/) (2024)
- [Self-Labeling the Job Shop Scheduling Problem](https://mlsanity.com/paper/2401.11849/) (2024)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [A Deep Reinforcement Learning Framework For Column Generation](https://mlsanity.com/paper/2206.02568/) (2022)
- [Finite Expression Method for Solving High-Dimensional Partial Differential Equations](https://mlsanity.com/paper/2206.10121/) (2022)
- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimization](https://mlsanity.com/paper/2310.15196/) (2023)
- [Variational Annealing on Graphs for Combinatorial Optimization](https://mlsanity.com/paper/2311.14156/) (2023)
- [Meta-Learning-Based Deep Reinforcement Learning for Multiobjective Optimization Problems](https://mlsanity.com/paper/2105.02741/) (2021)
- [Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning](https://mlsanity.com/paper/2301.03116/) (2023)

## Abstract (arXiv)

Many traditional algorithms for solving combinatorial optimization problems involve using hand-crafted heuristics that sequentially construct a solution. Such heuristics are designed by domain experts and may often be suboptimal due to the hard nature of the problems. Reinforcement learning (RL) proposes a good alternative to automate the search of these heuristics by training an agent in a supervised or self-supervised manner. In this survey, we explore the recent advancements of applying RL frameworks to hard combinatorial problems. Our survey provides the necessary background for operations research and machine learning communities and showcases the works that are moving the field forward. We juxtapose recently proposed RL methods, laying out the timeline of the improvements for each problem, as well as we make a comparison with traditional algorithms, indicating that RL models can become a promising direction for solving combinatorial problems.