mlsanityData to 7 Oct 2026

Reinforcement Learning for Combinatorial Optimization: A Survey

arXiv 2003.03600 ↗First posted 7 Mar 2020cs.LG math.CO math.OCcited by 235

Not on the map. Why?

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.

Key facts. Cited by 235 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Mar 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 29; 2022: 39; 2023: 40; 2024: 53; 2025: 45; 2026: 29.

235 papers.

Sort:

By area:

  1. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  2. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  3. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 82
  4. 2023BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimizationcited by 80
  5. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 77
  6. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 70
  7. 2022Winner Takes It All: Training Performant RL Populations for Combinatorial Optimizationcited by 57
  8. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  9. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 54
  10. 2024Optimized Feature Generation for Tabular Data via LLMs with Decision Tree Reasoningcited by 48
  11. 2024GraphArena: Evaluating and Exploring Large Language Models on Graph Computationcited by 48
  12. 2021Constructions in combinatorics via neural networkscited by 46
38 more
  1. 2021Boost then Convolve: Gradient Boosting Meets Graph Neural Networkscited by 42
  2. 2023Combinatorial Optimization with Policy Adaptation using Latent Space Searchcited by 41
  3. 2022On Representing Linear Programs by Graph Neural Networkscited by 39
  4. 2023OptiMUS: Optimization Modeling Using MIP Solvers and large language modelscited by 39
  5. 2024Diffusion Models as Constrained Samplers for Optimization with Unknown Constraintscited by 33
  6. 2021ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learningcited by 31
  7. 2022Challenges and Opportunities in Deep Reinforcement Learning with Graph Neural Networks: A Comprehensive review of Algorithms and Applicationscited by 27
  8. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  9. 2024Self-Labeling the Job Shop Scheduling Problemcited by 23
  10. 2024Bridging Evolutionary Algorithms and Reinforcement Learning: A Comprehensive Survey on Hybrid Algorithmscited by 23
  11. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  12. 2022A Deep Reinforcement Learning Framework For Column Generationcited by 21
  13. 2022Finite Expression Method for Solving High-Dimensional Partial Differential Equationscited by 21
  14. 2022SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problemscited by 21
  15. 2023Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimizationcited by 21
  16. 2023Variational Annealing on Graphs for Combinatorial Optimizationcited by 21
  17. 2021Meta-Learning-Based Deep Reinforcement Learning for Multiobjective Optimization Problemscited by 20
  18. 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learningcited by 19
  19. 2023Machine Learning for Cutting Planes in Integer Programming: A Surveycited by 19
  20. 2022Learning to Control Local Search for Combinatorial Optimizationcited by 18
  21. 2025Pareto Set Learning for Multi-Objective Reinforcement Learningcited by 18
  22. 2021Guidelines for the Computational Testing of Machine Learning approaches to Vehicle Routing Problemscited by 16
  23. 2022Reinforcement learning for automatic quadrilateral mesh generation: a soft actor-critic approachcited by 16
  24. 2022Learning to Solve Vehicle Routing Problems: A Surveycited by 16
  25. 2023Controlling Continuous Relaxation for Combinatorial Optimizationcited by 16
  26. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspectivecited by 16
  27. 2024The RL/LLM Taxonomy Tree: Reviewing Synergies Between Reinforcement Learning and Large Language Modelscited by 15
  28. 2021A Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Dronecited by 14
  29. 2022Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Explorationcited by 14
  30. 2022Neural Set Function Extensions: Learning with Discrete Functions in High Dimensionscited by 14
  31. 2024Multi-granular Adversarial Attacks against Black-box Neural Ranking Modelscited by 14
  32. 2025BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimizationcited by 14
  33. 2021Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problemscited by 13
  34. 2023Neural Multi-Objective Combinatorial Optimization with Diversity Enhancementcited by 13
  35. 2025ORFS-agent: Tool-Using Agents for Chip Design Optimizationcited by 13
  36. 2022Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branchcited by 12
  37. 2022ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learningcited by 11
  38. 2023Transformers in Reinforcement Learning: A Surveycited by 11

50 most cited of 235 All 235 (JSON)