Source-linked AI summary
Reinforcement Learning for Combinatorial Optimization: A Survey
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, Evgeny Burnaev
TL;DR
Hard combinatorial optimization problems often rely on approximate or heuristic algorithms, while evidence across the surveyed literature for RL-based approaches remains the focus of synthesis. The survey organizes RL methods through MDP-based solution pipelines, reviews applications across canonical problems, and compares them with traditional algorithms. It concludes that RL for combinatorial optimization is a promising research direction, while reported quality advantages are mainly established for less complex problem versions.
Problem
Many combinatorial optimization problems are NP-hard and therefore commonly require approximate or heuristic algorithms.
Method
The survey synthesizes RL approaches that reformulate combinatorial optimization as MDP-based sequential decision processes, review applications, and compare them with traditional algorithms.
Results
The survey concludes that RL for combinatorial optimization can be effective in solution quality, outperform existing algorithms, and achieve running-time gains over classical heuristics.
Takeaways & Limitations
RL for combinatorial optimization is presented as a promising direction, with unexplored joint and constructive algorithmic combinations identified for some problems.
Takeaways & Limitations
Reported solution-quality advantages and optimal-quality results are limited mainly to less complex problem versions, such as instances with fewer nodes.
Abstract
from arXiv · showhide
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.
1. Introduction
Combinatorial optimization problems often require approximate or heuristic methods because many are NP-hard. The survey presents reinforcement learning as a framework that models these problems as sequential decisions and learns solution-search policies through an MDP pipeline.
- Many combinatorial optimization problems are NP-hard, motivating approximate and heuristic algorithms rather than efficient polynomial-time solutions.
- RL models a combinatorial optimization problem as a sequential decision process in which an agent acts in an environment to construct a solution.An MDP provides the mathematical framework for this interaction.
- An MDP specifies states, actions, rewards, transitions, discounting, and episode horizon for the optimization task.States may represent partial solutions or iterative improvements, while actions add to or change solutions and rewards measure improvement or worsening.
- After MDP formulation, value-based methods select actions using estimated Q-values, whereas policy-based methods directly optimize a parameterized policy.
- The RL pipeline encodes states into numerical vectors, learns encoder parameters through an RL algorithm, repeatedly acts and receives rewards, then searches unseen instances after training.Encoders include recurrent, graph, attention-based, and multilayer-perceptron networks.
- The survey reviews RL applications to canonical problems including TSP, Max-Cut, MIS, MVC, and BPP, alongside related machine-learning and optimization work.
2. Background
This background introduces canonical combinatorial optimization problems, their formulations and classical solution methods, then explains how RL represents and solves them through learned state encoders and search procedures.
- 2.1. Combinatorial Optimization Problems: The survey covers MILP, TSP, Max-Cut, bin packing, minimum vertex cover, and maximum independent set as combinatorial optimization problems.These problems are presented with formal definitions, applications, complexity or approximation context, and state-of-the-art solution approaches.
- 2.1. Combinatorial Optimization Problems: TSP seeks a minimum-weight tour visiting every graph node exactly once, while existing approaches include Held–Karp, MILP solvers, Concorde, and LKH3.Held–Karp solves the general problem in O(n2^n), whereas Concorde combines cutting planes with branch-and-bound and LKH3 improves tours by rewiring edges.
- 2.2. Encoders: RL agents require encoders that transform problem states into numerical vectors, with recurrent, attention-based, pointer, and graph neural networks among the surveyed choices.GNNs update node representations through local message passing, while pointer networks select a single input element using similarity weights.
- 2.3.3. Monte Carlo Tree Search: The survey describes MCTS as selecting nodes by an upper confidence bound, evaluating new nodes with policy and value estimates, and backing values through the search tree.Tree nodes represent states and edges represent actions; neural networks provide policy and state-value estimates instead of rollout evaluation.
3. Taxonomy of RL for CO
The survey organizes RL approaches for combinatorial optimization along several complementary dimensions, including RL method family, integration with existing solvers, and solution-search strategy.
- RL method family: RL methods for CO can be classified by model-based versus model-free approaches, or by policy-based, value-based, and Monte-Carlo methods.
- Integration with CO solvers: Another taxonomy distinguishes principal learning, where the agent directly constructs a solution, from joint training with existing solvers.In principal learning, the agent receives reward from the constructed solution; in solver-integrated learning, it improves solver behavior.
- Examples: Table 1 summarizes approaches for the Travelling Salesman Problem.
- Integration with CO solvers: In Branch & Bound, an RL agent can learn node-selection policies because branching rules affect tree size and algorithm running time.The agent can receive rewards proportional to running time, replacing heuristics that typically rely on domain expertise or hyperparameter tuning.
- Solution-search strategy: RL approaches also differ according to whether they learn construction heuristics or improvement heuristics.Construction methods incrementally add elements to partial solutions, whereas improvement methods iteratively modify an initial solution.
4. RL for CO
The survey reviews reinforcement-learning approaches for canonical combinatorial optimization problems, covering constructive, improvement, joint, and hybrid methods. Across these problems, it describes varied MDP formulations, encoders, rewards, and reported comparisons with heuristics and established solvers.
- General approaches: RL approaches represent combinatorial optimization tasks as MDPs for constructing or improving solutions, with states encoding partial or current solutions and actions selecting solution changes.Examples include node selection for TSP, permutation-matrix output for permutation problems, and cut selection for branch-and-cut.
- Routing problems: Policy-gradient and encoder-decoder methods extend from TSP to VRP and related routing problems by adapting representations and rewards to dynamic demands and problem variants.VRP methods encode customer locations and time-varying demands, while attention-based and transformer-style architectures replace or modify recurrent encoders.
- Joint and hybrid methods: Hybrid methods combine reinforcement learning with constraint programming, cutting planes, supervised learning, or classical heuristics to learn branching, orientation, cut-selection, or improvement policies.Examples include RL-trained branching strategies for several CP searches, multi-task orientation learning, and joint PPO–simulated-annealing optimization.
- General frameworks: A general model-free framework uses edge-to-vertex line graphs, a GIN encoder, and an attention decoder to adapt reinforcement learning across problem classes by changing the reward.The framework also learns the policy during tree search rather than relying on a separate full-featured Neural MCTS.
- Reported results: Reported results include better performance than several heuristics or prior approaches, smaller bin-gap ratios up to 30 items, smaller optimality gaps up to 500 nodes, and scaling to graphs of 100,000 nodes.The cited studies report these outcomes for bin packing, minimum vertex cover, and budget-constrained maximum vertex cover settings.
5. Comparison
The survey compares RL methods with baselines on TSP and CVRP, finding competitive performance while noting limitations in graph size, problem overlap, and runtime comparability.
- Comparison setup: RL methods are compared on TSP and CVRP using average tour lengths, with OR-Tools and LK-H included as baseline solutions.The TSP comparison covers ER graphs with 20, 50, and 100 nodes; CVRP covers 10, 20, 50, and 100 nodes with vehicle capacities from 10 to 50.
- Best-performing methods: The best-performing TSP methods are and [Bello et al., 2017], while performs best for VRP.These methods perform on par with the baselines and sometimes achieve better results.
- Best-performing methods: achieves the best performance across the compared methods, including tasks with smaller vehicle capacities.
- Graph size: Most studies evaluate graphs with 20, 50, or 100 nodes, whereas [Ma et al., 2020] also reports TSP results for graphs with 250 to 1000 nodes.For smaller graphs, almost all methods outperform OR-Tools; for bigger graphs, this is no longer the case.
- Comparison limitations: Comparisons are difficult because the reviewed studies rarely address the same combinatorial optimization problems.The survey calls for unified results from different sources to identify promising research directions.
- Running times: Runtime comparisons remain difficult because implementations and experimental hardware vary substantially across studies.Some works claim faster runtimes than classic heuristics, including for larger problems, but the survey does not exactly compare reported times.
6. Conclusion and future directions
The survey concludes that RL is promising for combinatorial optimization because reviewed methods can match or outperform classical approaches and reduce running times. It identifies generalization, solution quality, and unexplored algorithmic combinations as priorities for future work.
- Conclusion: RL methods are reported to perform on par with state-of-the-art heuristic methods and solvers, with solution-quality and running-time advantages in the survey’s conclusion.
- Generalization to other problems: Generalization remains limited because current RL-CO approaches often require implementation for concrete problem sets.Potential unseen problems include smaller instances, different distributions, and other combinatorial optimization problem groups.
- Improving the solution quality: Solution-quality results equal to optimal or heuristic solutions are mainly reported for less complex problems with smaller numbers of nodes.The survey suggests incorporating classical combinatorial optimization algorithms with RL, including imitation learning.
- Filling the gaps: The reviewed classifications reveal unexplored combinations of joint and constructive approaches for Bin Packing and Minimum Vertex Problem.Exploring these combinations may produce new methods and insights into their effectiveness.
- Conclusion: The survey presents RL for combinatorial optimization as promising because of solution quality, the capacity to outperform existing algorithms, and running-time gains over classical heuristics.