Reinforcement Learning for Combinatorial Optimization: A Survey

Combinatorial optimization (CO) is the workhorse of numerous important applications in operations research, engineering, and other fields and, thus, has been attracting enormous attention from the research community recently. Some efficient approaches to common problems involve using hand-crafted heuristics to sequentially construct a solution. Therefore, it is intriguing to see how a CO problem can be reformulated as a sequential decision-making process, and whether these heuristics can be implicitly learned by a reinforcement learning (RL) agent. This survey explores the synergy between the CO and RL frameworks, which can become a promising direction for solving combinatorial problems.

• Publication year

  2020

• Venue

  Computers & Operations Research

• Publication date

  2020-03-07

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.cor.2021.105400arXiv 2003.03600
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Deep Learning Algorithm for the Max-Cut Problem Based on Pointer Network Structure with Supervised Learning and Reinforcement Learning Strategies

  2020cited by this paper
• Learn to Design the Heuristics for Vehicle Routing Problem

  2020cited by this paper
• Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time

  2020cited by this paper
• IBM ILOG CPLEX Optimization Studio

  2020cited by this paper
• Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization

  2020influential reference
• Reinforcement learning enhanced quantum-inspired algorithm for combinatorial optimization

  2020cited by this paper
• A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem

  2020cited by this paper
• Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning

  2020cited by this paper
• A Learning-based Iterative Method for Solving Vehicle Routing Problems

  2020influential reference
• Learning Combinatorial Optimization on Graphs: A Survey With Applications to Networking

  2020cited by this paper
• A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems

  2020cited by this paper
• The SCIP Optimization Suite 7.0

  2020cited by this paper
• A State Aggregation Approach for Solving Knapsack Problem with Deep Reinforcement Learning

  2020cited by this paper
• GCOMB: Learning Budget-constrained Combinatorial Algorithms over Billion-sized Graphs

  2020cited by this paper
• Fast Detection of Maximum Common Subgraph via Deep Q-Learning

  2020cited by this paper
• Co-training for Policy Learning

  2019influential reference
• Deep Auto-Deferring Policy for Combinatorial Optimization

  2019cited by this paper
• Exploratory Combinatorial Optimization with Reinforcement Learning

  2019influential reference
• Automated quantum programming via reinforcement learning for combinatorial optimization

  2019cited by this paper
• Solving Packing Problems by Conditional Query Learning

  2019cited by this paper
• Learning Self-Game-Play Agents for Combinatorial Optimization Problems

  2019cited by this paper
• Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero

  2019cited by this paper
• Mastering Atari, Go, chess and shogi by planning with a learned model

  2019cited by this paper
• Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning

  2019influential reference
• Reinforcement-Learning-Based Variational Quantum Circuits Optimization for Combinatorial Problems

  2019cited by this paper
• Vine copula structure learning via Monte Carlo tree search

  2019cited by this paper
• Reinforcement Learning for Integer Programming: Learning to Cut

  2019cited by this paper
• Reinforcement Learning Driven Heuristic Optimization

  2019cited by this paper
• Coloring Big Graphs with AlphaGoZero

  2019cited by this paper
• Annealing by simulating the coherent Ising machine.

  2019cited by this paper
• Solving Combinatorial Problems with Machine Learning Methods

  2019cited by this paper
• A Comprehensive Survey on Graph Neural Networks

  2019cited by this paper
• Learning Improvement Heuristics for Solving Routing Problems

  2019cited by this paper
• How Powerful are Graph Neural Networks?

  2018cited by this paper
• A Multi-task Selected Learning Approach for Solving 3D Flexible Bin Packing Problem

  2018cited by this paper
• Reinforcement Learning for Solving the Vehicle Routing Problem

  2018cited by this paper
• Coherent Ising Machine - Optical Neural Network Operating at the Quantum Limit -

  2018cited by this paper
• Destabilization of Local Minima in Analog Spin Systems by Correction of Amplitude Heterogeneity.

  2018cited by this paper
• Attention, Learn to Solve Routing Problems!

  2018cited by this paper
• Set Transformer

  2018cited by this paper
• Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion

  2018cited by this paper
• Latent Space Policies for Hierarchical Reinforcement Learning

  2018cited by this paper
• Decision diagrams for optimization

  2018cited by this paper
• Vehicle Routing Problems

  2018cited by this paper
• Graph Neural Networks: A Review of Methods and Applications

  2018cited by this paper
• Learning Goal Embeddings via Self-Play for Hierarchical Reinforcement Learning

  2018cited by this paper
• Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon

  2018cited by this paper
• Learning Representations in Model-Free Hierarchical Reinforcement Learning

  2018cited by this paper
• Learning Permutations with Sinkhorn Policy Gradient

  2018cited by this paper
• Improving Optimization Bounds using Machine Learning: Decision Diagrams meet Deep Reinforcement Learning

  2018influential reference
• Boosting Combinatorial Problem Modeling with Machine Learning

  2018cited by this paper
• Integer Programming

  2018influential reference
• Learning to Perform Local Rewriting for Combinatorial Optimization

  2018cited by this paper
• Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization

  2018cited by this paper
• Learning Heuristics for the TSP by Policy Gradient

  2018cited by this paper
• Proximal Policy Optimization Algorithms

  2017cited by this paper
• An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems: Technical report

  2017cited by this paper
• Learning Combinatorial Optimization Algorithms over Graphs

  2017influential reference
• Solving a New 3D Bin Packing Problem with Deep Reinforcement Learning Method

  2017cited by this paper
• Learning Generalized Reactive Policies using Deep Neural Networks

  2017cited by this paper
• Graph Attention Networks

  2017cited by this paper
• Attention is All you Need

  2017influential reference
• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm

  2017cited by this paper
• Deep Q-learning From Demonstrations

  2017cited by this paper
• Neural Message Passing for Quantum Chemistry

  2017cited by this paper
• Thinking Fast and Slow with Deep Learning and Tree Search

  2017cited by this paper
• Financial Portfolio Management using D-Wave’s Quantum Optimizer: The Case of Abu Dhabi Securities Exchange

  2017cited by this paper
• Discriminative Embeddings of Latent Variable Models for Structured Data

  2016cited by this paper
• Mastering the game of Go with deep neural networks and tree search

  2016cited by this paper
• Semi-Supervised Classification with Graph Convolutional Networks

  2016cited by this paper
• Neural Combinatorial Optimization with Reinforcement Learning

  2016influential reference
• The Option-Critic Architecture

  2016cited by this paper
• Asynchronous Methods for Deep Reinforcement Learning

  2016cited by this paper
• Self-Critical Sequence Training for Image Captioning

  2016cited by this paper
• Human-level control through deep reinforcement learning

  2015cited by this paper
• Deep Learning

  2015cited by this paper
• Pointer Networks

  2015cited by this paper
• Finding near-optimal independent sets at scale

  2015cited by this paper
• Continuous control with deep reinforcement learning

  2015cited by this paper
• Graph Partitioning for Independent Sets

  2015cited by this paper
• Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover

  2014cited by this paper
• Learning Phrase Representations using RNN Encoder–Decoder for Statistical Machine Translation

  2014cited by this paper
• Improved Bin Completion for Optimal Bin Packing and Number Partitioning

  2013cited by this paper
• Bin packing problem

  2013cited by this paper
• Exact Algorithms for Maximum Independent Set

  2013cited by this paper
• ColPack: Software for graph coloring and related problems in scientific computing

  2013cited by this paper
• A hybrid genetic algorithm with a new packing strategy for the three-dimensional bin packing problem

  2012cited by this paper
• GLPK (GNU Linear Programming Kit)

  2012cited by this paper
• Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness

  2012cited by this paper
• A Survey of Monte Carlo Tree Search Methods

  2012cited by this paper
• Finding low-energy conformations of lattice protein models by quantum annealing

  2012cited by this paper
• Dynamic Local Search for the Maximum Clique Problem

  2011cited by this paper
• Handbook of Approximation Algorithms and Metaheuristics

  2010cited by this paper
• Three-dimensional bin packing problem with variable bin height

  2010cited by this paper
• Efficient graphlet kernels for large graph comparison

  2009cited by this paper
• Z3: An Efficient SMT Solver

  2008cited by this paper
• Fast local search for the maximum independent set problem

  2008cited by this paper
• Extreme Point-Based Heuristics for Three-Dimensional Bin Packing

  2008cited by this paper
• Et al

  2008influential reference
• Combinatorial Optimisation of Worm Propagation on an Unknown Network

  2007cited by this paper

• Toward Diffusion-Based Deep Reinforcement Learning for Discrete Decision-Making: Methods and Evaluations

  2026cites this paper
• Stochastic dynamic inventory-routing: A comprehensive review

  2026cites this paper
• A Reinforcement Learning Framework for Solving the Maximum Weighted Target Cover Problem with Distance Limitations

  2026cites this paper
• Strategic coordination of drones via short-term distributed optimization and long-term reinforcement learning

  2026cites this paper
• Energy-aware flexible open shop scheduling with multi-load automated guided vehicle by graph reinforcement learning assisted memetic algorithm

  2026cites this paper
• Graph Neural Network-Based Identification of Vulnerable Regions in Spatial Complex Networks via Virtual Nodes Model

  2026cites this paper
• Formulating the Electric Bus Fleet Scheduling Problem for Reinforcement Learning

  2026cites this paper
• Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling

  2026cites this paper
• An Attention-Based Learning Approach for Joint Optimization of Storage Selection and Order Picking Paths in Mobile Shelving Systems

  2026cites this paper
• A hybrid deep reinforcement learning approach for target allocation and routing of multiple nonholonomic vehicles

  2026cites this paper
• A Hybrid Optimization Approach for Multi-Generation Intelligent Breeding Decisions

  2026cites this paper
• Multicriteria VNF placement and chaining with machine learning: a survey and new opportunities for the AHP in decision-making scenarios

  2026cites this paper
• Solving Dynamic Job Shop Scheduling Problems via an enhanced Proximal Policy Optimization algorithm with Double Prioritized Experience Replay

  2026cites this paper
• Using Reinforcement Learning to Boost Grey Wolf Optimizer for Influence Maximization in Social Networks

  2026cites this paper
• ROI-Reasoning: Rational Optimization for Inference via Pre-Computation Meta-Cognition

  2026cites this paper
• Integrated multi-factory production scheduling and vehicle routing with factory eligibility

  2026cites this paper
• RLGT: A reinforcement learning framework for extremal graph theory

  2026cites this paper
• MME: Mixture of Mesh Experts with Random Walk Transformer Gating

  2026cites this paper
• Survey on Neural Routing Solvers

  2026cites this paper
• Optimal Multi-Debris Mission Planning in LEO: A Deep Reinforcement Learning Approach with Co-Elliptic Transfers and Refueling

  2026cites this paper
• Cross-Domain Deep Reinforcement Learning for Real-Time Resource Allocation in Transportation Hubs: From Airport Gates to Seaport Berths

  2026cites this paper
• Reinforcement Learning-Based Resource Allocation for Smart Vehicular Networks: A Review

  2026cites this paper
• Multi-Layer Scheduling in Gig Platforms Using a Generative Diffusion Model With Duality Guidance

  2026cites this paper
• Enabling Population-Based Architectures for Neural Combinatorial Optimization

  2026cites this paper
• An LLM-guided structural optimization method for aero-engine lubrication hydrocyclones

  2026cites this paper
• Designing Time Series Experiments in A/B Testing with Transformer Reinforcement Learning

  2026cites this paper
• Advanced Graph Neural Networks for Smart Mining: A Systematic Literature Review of Equivariant, Topological, Symplectic, and Generative Models

  2026cites this paper
• Digital twin-enabled nested Q-learning for multi-layer production planning and inventory control

  2026cites this paper
• Can machine learning help in solving the pallet loading optimization problem?

  2026cites this paper
• C2-SeqRL: Reinforcement Learning for Conflict-Constrained Sequence Construction

  2026cites this paper
• Constrained Semi-MDP Formulation and Perception-Enhanced Safe Policy Learning for Efficient Dynamic Task Scheduling of Data Centers

  2026cites this paper
• A hybrid AWQMIX-MGT algorithm integrating deep reinforcement learning and collaborative optimization strategies for ship equipment and pipe layout design

  2026cites this paper
• Applying Deep Reinforcement Learning to Minimize Flow Fluctuations in Digital Flow Control

  2025cites this paper
• Dual-Engine Intelligent Caching: A Joint Optimization Framework for 360° Mobile VR Video Edge Caching

  2025cites this paper
• Onboard Mission Replanning for Adaptive Cooperative Multi-Robot Systems

  2025cites this paper
• Bio inspired optimization techniques for disease detection in deep learning systems

  2025influential citation
• Neural combinatorial optimization: A tutorial

  2025cites this paper
• Demand Selection for VRP with Emission Quota

  2025cites this paper
• ORFS-agent: Tool-Using Agents for Chip Design Optimization

  2025cites this paper
• Deep reinforcement learning algorithm incorporating problem characteristics for dynamic multi-objective permutation flow-shop scheduling problem

  2025cites this paper
• VastPipe: A High-Throughput Inference System via Adaptive Space-Division Multiplexing for Diverse Accelerators

  2025cites this paper
• Reinforcement Learning for AMR Charging Decisions: The Impact of Reward and Action Space Design

  2025cites this paper
• Combinatorial optimization: From deep learning to large language models

  2025cites this paper
• A Reinforcement Learning Method to Factual and Counterfactual Explanations for Session-based Recommendation

  2025cites this paper
• Optimizing Drone Deployment for Maximized User Connectivity in Areas of Interest Via Deep Reinforcement Learning

  2025cites this paper
• Using Deep Reinforcement Learning to Decide Test Length

  2025cites this paper
• Deep Symbolic Optimization: Reinforcement Learning for Symbolic Mathematics

  2025cites this paper
• A survey on Machine learning algorithms in autonomous multiple unmanned aerial vehicles (UAVs) in wireless networks

  2025cites this paper
• Large Language Model-Assisted Deep Reinforcement Learning from Human Feedback for Job Shop Scheduling

  2025cites this paper
• SchedulExpert: Graph Attention Meets Mixture-of-Experts for JSSP

  2025cites this paper
• Unraveling the Rainbow: can value-based methods schedule?

  2025cites this paper
• A Reinforcement Learning-Based Iterative Method for Capacitated Hub Location Problems in UAV Networks

  2025cites this paper
• USPR: Learning a Unified Solver for Profiled Routing

  2025cites this paper
• A Generative Neural Annealer for Black-Box Combinatorial Optimization

  2025cites this paper
• RIDGECUT: Learning Graph Partitioning with Rings and Wedges

  2025cites this paper
• Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problems

  2025cites this paper
• Flexible Job Shop Scheduling Problem using graph neural networks and reinforcement learning

  2025cites this paper
• URB - Urban Routing Benchmark for RL-equipped Connected Autonomous Vehicles

  2025cites this paper
• Learning to Search for Vehicle Routing with Multiple Time Windows

  2025cites this paper
• DOPPLER: Dual-Policy Learning for Device Assignment in Asynchronous Dataflow Graphs

  2025cites this paper
• Dynamical mechanisms of growth-feedback effects on adaptive gene circuits

  2025cites this paper
• Solving the traveling salesman problem with machine learning: a review of recent advances and challenges

  2025cites this paper
• Dependent-Chance Goal Programming for Sustainable Supply Chain Design: A Reinforcement Learning-Enhanced Salp Swarm Approach

  2025cites this paper
• Leveraging graph neural networks and multi-agent reinforcement learning for inventory control in supply chains

  2025cites this paper
• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms

  2025cites this paper
• Deep Reinforcement Learning for Selecting the Optimal Hybrid Cloud Placement Combination of Standard Enterprise IT Applications

  2025cites this paper
• Towards VM Rescheduling Optimization Through Deep Reinforcement Learning

  2025cites this paper
• TuneNSearch: a hybrid transfer learning and local search approach for solving vehicle routing problems

  2025cites this paper
• Efficient optimal power flow learning: A deep reinforcement learning with physics-driven critic model

  2025cites this paper
• Revisiting Location Privacy in MEC-Enabled Computation Offloading

  2025cites this paper
• Causal Discovery and Inference towards Urban Elements and Associated Factors

  2025cites this paper
• Reinforcement learning with combinatorial actions for coupled restless bandits

  2025cites this paper
• BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization

  2025cites this paper
• Arbitrarily shaped spatial cluster detection via reinforcement learning algorithms

  2025cites this paper
• Neural combinatorial optimization with reinforcement learning in industrial engineering: a survey

  2025cites this paper
• Machine Learning-Based Autonomous Optimization of Unattended Wireless Sensor Networks Through Multi-Cause Reinforcement Learning

  2025cites this paper
• A graph attention-based policy gradient method with an adaptive embedding strategy for k-center problems

  2025cites this paper
• Learning-based hybrid algorithms for container relocation problem with storage plan

  2025cites this paper
• Network extension planning towards resilient urban critical infrastructures using deep reinforcement learning

  2025cites this paper
• Reinforcement Learning for Efficient Drone-Assisted Vehicle Routing

  2025cites this paper
• Solving online resource-constrained scheduling for follow-up observation in astronomy: A reinforcement learning approach

  2025cites this paper
• Defending Against APT Attacks in Cloud Computing Environments Using Grouped Multiagent Deep Reinforcement Learning

  2025cites this paper
• Solving Multiobjective Combinatorial Optimization via Learning to Improve Method

  2025cites this paper
• Multi-strategy fusion novel binary equalization optimizer with dynamic transfer function for high-dimensional feature selection

  2025cites this paper
• Attention ensemble mixture: a novel offline reinforcement learning algorithm for autonomous vehicles

  2025cites this paper
• Causality Enhanced Origin-Destination Flow Prediction in Data-Scarce Cities

  2025cites this paper
• Generative Diffusion Model-based Energy Management in Networked Energy Systems

  2025cites this paper
• Tree Search Reinforcement Learning for Two-Dimensional Cutting Stock Problem With Complex Constraints

  2025cites this paper
• Combining Reinforcement Learning and Heuristic Optimization: A Model Based on a Deep Q-Network and Graph Neural Networks for Graph Coloring

  2025cites this paper
• Harnessing heterogeneous graph neural networks for Dynamic Job-Shop Scheduling Problem solutions

  2025cites this paper
• Reinforcement Learning for Solving the Pricing Problem in Column Generation: Applications to Vehicle Routing

  2025cites this paper
• PixelCraftSR: Efficient Super-Resolution with Multi-Agent Reinforcement for Edge Devices

  2025cites this paper
• Reinforcement learning for healthcare operations management: methodological framework, recent developments, and future research directions

  2025cites this paper
• Hybrids of Reinforcement Learning and Evolutionary Computation in Finance: A Survey

  2025cites this paper
• ProtoRAIL: A Risk-cognizant Imitation Agent for Adaptive vCPU Oversubscription In the Cloud

  2025cites this paper
• Combinatorial Optimization Algorithms in Tourism Planning and Emergency Management and Their Application to Resource Allocation

  2025cites this paper
• Attention enhanced reinforcement learning for flexible job shop scheduling with transportation constraints

  2025cites this paper
• MaxCutBench: Revisiting and Benchmarking Graph Neural Networks for Maximum Cut

  2025cites this paper
• A novel reward-based golden jackal optimization algorithm uses mix-weighted dynamic and random opposition learning to solve optimization problems

  2025cites this paper
• A Cost-Aware Adaptive Bike Repositioning Agent Using Deep Reinforcement Learning

  2025cites this paper