RL for Combinatorial Optimization

RL: Reinforcement Learning

Ask about this topic

Overview

This field uses reinforcement learning (RL) to build or improve solutions to problems such as vehicle routing, job-shop scheduling, packing, and graph design, where choices interact and the search space grows rapidly. Common approaches train policies with PPO or policy gradients using graph neural networks or Transformers, and increasingly combine RL with local search, evolutionary methods, exact optimization, or tree search. Research also focuses on dynamic settings, changing constraints, and generalizing from small training instances to larger or unfamiliar problems. A central tension is whether learned methods can match strong specialized heuristics and exact solvers in solution quality while offering faster decisions and reliable feasibility at scale.

Latest papers

CardsList

106 papers18 papers in the last four weeks, up 80% on the four weeks before. 0.1% of all new papers.

  1. Learning to Place Guards by Reinforcement: A Geo-Free Neural Policy for the Vertex-Guard Art Gallery Problem

    Jun 19, 2026Domagoj Ševerdija, Jurica Maltar, Nathan Chappel +1Representation ProbingRL for Combinatorial Optimization

    School of Applied Mathematics and Informatics, University J. J. Strossmayer of Osijek, Croatia

  2. N(CO)2^2: Neural Combinatorial Optimization with Chance Constraints to Solve Stochastic Orienteering

    Jun 16, 2026Anas Saeed, Marcos Abel Zuzuárregui, Stefano CarpinStochastic OptimizationChance-Constrained Optimization

    Department of Computer Science and Engineering, University of California, Merced, CA, USA

  3. Deep Reinforcement Learning for Minimum Zero-Forcing Sets

    Jun 16, 2026Steve Halley, Maurício GruppiReinforcement LearningCombinatorial Optimization

    Department of Computing Sciences, Villanova University Villanova, Pennsylvania, USA

  4. Discovering Lattice Reduction Strategies via Self-Play

    Jun 13, 2026Mohamed Malhou, Kristin Lauter, Ludovic PerretReinforcement LearningRL for Combinatorial Optimization

    FAIR, Meta Superintelligence Labs & Sorbonne Université CNRS, LIP6 Paris, France · EPITA, EPITA Research Lab (LRE) Le Kremlin-Bicêtre, France

  5. Geometry-Aware Reinforcement Learning for 2D Irregular Nesting

    Jun 9, 2026Auguste Lehuger, Guillaume Henon-JustReinforcement LearningGeometric Representation Learning

    Valeo Brain

  6. Baseline-Free Policy Optimization for Neural Combinatorial Optimization

    Jun 9, 2026Carlos S. Sepúlveda, Gonzalo A. RuzTraveling Salesperson ProblemGroup Relative Policy Optimization

    Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez Millennium Nucleus for Social Data Science (SODAS) Millennium Nucleus in Data Science for Plant Resilience (PhytoLearning) Santiago, Chile

  7. TriSearch: Learning to Optimize Triangulations via Bistellar Flips

    May 28, 2026Yiran Wang, Guido MontúfarReinforcement LearningRL for Combinatorial Optimization

    UCLA · MPI MiS

  8. Towards Generalization-Oriented Models for Vehicle Routing Problems with Mixture-of-Experts

    May 26, 2026Changhao Miao, Yuntian Zhang, Tongyu Wu +2Reinforcement LearningAdaptive Model Routing

    State Key Laboratory of Autonomous Intelligent Unmanned Systems, Beijing Institute of Technology, Beijing 100081, China · Department of Computer, Control and Management Engineering “Antonio Ruberti”, Sapienza University of Rome, Rome, 00185, Italy · School of AI, Beijing Institute of Technology, Beijing 100081, China

  9. MVR-cache: Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation

    May 24, 2026Ali Noshad, Zishan Zheng, Yinjun WuLLM Inference EfficiencyRL for Combinatorial Optimization

    School of Computer Science, Peking University, Beijing, China · School of Information, Renmin University of China, Beijing, China

  10. Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimization

    May 19, 2026Franco Terranova, Guillermo Bernardez, Albert Cabellos-Aparicio +2Latent Action LearningCombinatorial Optimization

    UL, LORIA, RESIST · UC Santa Barbara - UCSB · UPC +1

  11. Scheduling That Speaks: An Interpretable Programmatic Reinforcement Learning Framework

    May 18, 2026Chengpeng Hu, Yingqian Zhang, Hendrik BaierReinforcement LearningInterpretable ML

    Eindhoven University of Technology, Eindhoven, the Netherlands · Centrum Wiskunde & Informatica, Amsterdam, the Netherlands

  12. Beyond Inference-Time Search: Reinforcement Learning Synthesizes Reusable Solvers

    May 18, 2026Soheyl Massoudi, Gabriel Apaza, Milad Habibi +1RL for Code GenerationLLM-Based Program Synthesis

    ETH Zürich Zürich, Switzerland · University of Maryland College Park, MD, USA

  13. Learning Multi-Timescale Abstractions for Hierarchical Combinatorial Planning

    May 16, 2026Vivienne Huiling Wang, Tinghuai Wang, Joni PajarinenWorld Model-Based PlanningHierarchical RL

    Department of Electrical Engineering and Automation, Aalto University, Finland · Qutwo, Finland

  14. A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problems

    May 14, 2026Wen Wang, Xiangchen Wu, Liang Wang +2Reinforcement LearningVehicle Routing

    Nanjing University

  15. Learning Minimally Rigid Graphs with High Realization Counts

    May 12, 2026Oleksandr Slyvka, Jan Rubeš, Rodrigo Alves +1RL for Combinatorial OptimizationGraph Construction

    Faculty of Information Technology, Czech Technical University in Prague, Czechia · ETH ZÜrich, Switzerland

  16. Automated co-design of high-performance thermodynamic cycles via graph-based hierarchical reinforcement learning

    Apr 14, 2026Wenqing Li, Xu Feng, Peixue Jiang +1Reinforcement LearningRL for Combinatorial Optimization

    Key Laboratory for Thermal Science and Power Engineering of Ministry of Education, Beijing Key Laboratory of CO2 Utilization and Reduction Technology, Department of Energy and Power Engineering, Tsinghua University, Beijing, 100084, China · Shanxi Research Institute for Clear Energy Tsinghua University, Taiyuan, 030032, China

  17. Diffusion Reinforcement Learning Based Online 3D Bin Packing Spatial Strategy Optimization

    Apr 13, 2026Jie Han, Tong Li, Qingyang Xu +3RL for Combinatorial Optimization

    School of Mechanical, Electrical, and Information Engineering, Shandong University, Weihai 264209, China · Shandong Key Laboratory of Intelligent Electronic Packaging Testing and Application, Shandong University, Weihai 264209, China

  18. A First Guess is Rarely the Final Answer: Learning to Search in the Traveling Salesperson Problem

    Apr 8, 2026Andoni Irazusta GarmendiaTraveling Salesperson ProblemNeural Combinatorial Optimization

    University of the Basque Country (UPV/EHU)

  19. Vehicle-as-Prompt: A Unified Deep Reinforcement Learning Framework for Heterogeneous Fleet Vehicle Routing Problem

    Apr 6, 2026Shihong Huang, Shengjie Wang, Lei Gao +4Vehicle RoutingRL for Combinatorial Optimization

    Polytechnic Institute, Zhejiang University, 310015, Hangzhou, China · S.F. Technology Co., Ltd., 518054, Shenzhen, China · School of Management, Zhejiang University, 310058, Hangzhou, China

  20. Critic-Free Deep Reinforcement Learning for Maritime Coverage Path Planning on Irregular Hexagonal Grids

    Mar 30, 2026Carlos S. Sepúlveda, Gonzalo A. RuzPointer NetworksCoverage Path Planning

    Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Av. Diagonal las Torres 2640, Santiago, Chile · Dirección de Programas, Investigación y Desarrollo, Armada de Chile, General del Canto 398, Valparaíso, Chile · Millennium Nucleus for Social Data Science (SODAS), Santiago, Chile +1

  21. Dynamic resource matching in manufacturing using deep reinforcement learning

    Mar 28, 2026Saunak Kumar Panda, Yisha Xiang, Ruiqi LiuManufacturingRL for Combinatorial Optimization

    Department of Industrial Engineering, University of Houston, Houston, TX 77004, USA · Department of Mathematics and Statistics, Texas Tech University, Lubbock, TX 79409, USA

  22. A Deep Reinforcement Learning (DRL)-Based Transformer Method for Solving the Open Shop Scheduling Problem

    Mar 25, 2026Faezeh Ardali, Mwembezi A. Nyelele, Gerald M. KnappCombinatorial OptimizationNeural Combinatorial Optimization

    Louisiana State University, Baton Rouge, LA, USA · University of Minnesota Duluth, Duluth, MN, USA

  23. The DeepXube Software Package for Solving Pathfinding Problems with Learned Heuristic Functions and Search

    Mar 25, 2026Forest AgostinelliAutomated Heuristic DesignGraph-Based Planning

    Department of Computer Science and Engineering University of South Carolina

  24. A Learning Method with Gap-Aware Generation for Heterogeneous DAG Scheduling

    Mar 24, 2026Ruisong Zhou, Haijun Zou, Li Zhou +2Neural Combinatorial OptimizationRL for Combinatorial Optimization

    School of Mathematical Science, Peking University, Beijing 100871, China · State Key Laboratory of Mathematical Sciences, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China · Theory Lab, Central Research Institute, 2012 Labs, Huawei Technologies Co., Ltd, China +1

  25. Decoupling Numerical and Structural Parameters: An Empirical Study on Adaptive Genetic Algorithms via Deep Reinforcement Learning for the Large-Scale TSP

    Mar 21, 2026Hongyu Wang, Yuhan Jing, Yibing Shi +3Evolutionary OptimizationGenetic Algorithms

    School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, China · School of Mechanical Engineering, Xi’an Jiaotong University, Xi’an, China · Frontier Institute of Science and Technology, Xi’an Jiaotong University, Xi’an, China

  26. Approximate Subgraph Matching with Neural Graph Representations and Reinforcement Learning

    Mar 18, 2026Kaiyang Li, Shihao Ji, Zhipeng Cai +1RL for Combinatorial Optimization

    University of Connecticut, 352 Mansfield Road, Storrs, CT 06269, USA · Georgia State University, 33 Gilmer Street SE, Atlanta, GA 30303, USA

  27. Deep Reinforcement Learning for Fano Hypersurfaces

    Mar 16, 2026Marc TruterRL for Combinatorial Optimization

  28. Cluster-Aware Attention-Based Deep Reinforcement Learning for Pickup and Delivery Problems

    Mar 9, 2026Wentao Wang, Lifeng Han, Guangyu ZouVehicle RoutingRL for Combinatorial Optimization

    Leicester International Institute, Dalian University of Technology, Panjin, 124221, Liaoning, China. · Department of Electronic and Information Technology, Dalian University of Technology, Panjin, 124221, Liaoning, China.

  29. Dynamic Vehicle Routing Problem with Prompt Confirmation of Advance Requests

    Mar 8, 2026Amutheezan Sivagnanam, Ayan Mukhopadhyay, Samitha Samaranayake +2Vehicle RoutingRL for Combinatorial Optimization

    Department of Informatics and Intelligent Systems, Pennsylvania State University, University Park, Pennsylvania · Department of Computer Science, College of William & Mary, Williamsburg, Virginia · School of Civil and Environmental Engineering, Cornell University, Ithaca, New York +1

  30. RESCHED: Rethinking Flexible Job Shop Scheduling from a Transformer-based Architecture with Simplified States

    Mar 7, 2026Xiangjie Xiao, Cong Zhang, Wen Song +1Flexible Job Shop SchedulingJob Shop Scheduling

    School of Computing and Information Systems, Singapore Management University, Singapore · College of Computing and Data Science, Nanyang Technological University, Singapore · Institute of Marine Science and Technology, Shandong University, China