mlsanityData to 14 Oct 2026

Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation

arXiv 2412.10163 ↗First posted 13 Dec 2024cs.LG cs.AIcited by 2

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

Abstract (arXiv)

We introduce Limited Rollout Beam Search (LRBS), a beam search strategy for deep reinforcement learning (DRL) based combinatorial optimization improvement heuristics. Utilizing pre-trained models on the Euclidean Traveling Salesperson Problem, LRBS significantly enhances both in-distribution performance and generalization to larger problem instances, achieving optimality gaps that outperform existing improvement heuristics and narrowing the gap with state-of-the-art constructive methods. We also extend our analysis to two pickup and delivery TSP variants to validate our results. Finally, we employ our search strategy for offline and online adaptation of the pre-trained improvement policy, leading to improved search performance and surpassing recent adaptive methods for constructive heuristics.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 26 of its 48 references that are in the map. First posted on arXiv 13 Dec 2024.

Builds on

26 of 48 references.

References · 26

  1. 2015Pointer Networkscited by 895
  2. 2018Attention, Learn to Solve Routing Problems!cited by 656
  3. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  4. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  5. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  6. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 348
  7. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 269
  8. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 221
  9. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 164
  10. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 142
  11. 2021Learning to Delegate for Large-scale Vehicle Routingcited by 109
  12. 2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
14 more
  1. 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 103
  2. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  3. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 100
  4. 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
  5. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  6. 2019Exploratory Combinatorial Optimization with Reinforcement Learningcited by 82
  7. 2023BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimizationcited by 82
  8. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  9. 2019Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learningcited by 78
  10. 2022Winner Takes It All: Training Performant RL Populations for Combinatorial Optimizationcited by 58
  11. 2022Efficient Neural Neighborhood Search for Pickup and Delivery Problemscited by 29
  12. 2023Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimizationcited by 23
  13. 2018Boosting Combinatorial Problem Modeling with Machine Learningcited by 15
  14. 2021SOLO: Search Online, Learn Offline for Combinatorial Optimization Problemscited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2026CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimizationcited by 2
  2. 2025Multi-Dimensional AGV Path Planning in 3D Warehouses Using Ant Colony Optimization and Advanced Neural Networkscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement
  2. 2025ASAP: Exploiting the Satisficing Generalization Edge in Neural Combinatorial Optimization
  3. 2026Offline Decision Transformers for Neural Combinatorial Optimization: Surpassing Heuristics on the Traveling Salesman Problem
  4. 2025Heuristics for Combinatorial Optimization via Value-based Reinforcement Learning: A Unified Framework and Analysis
  5. 2024Transform then Explore: a Simple and Effective Technique for Exploratory Combinatorial Optimization with Reinforcement Learning
  6. 2022Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch
  7. 2025Preference Optimization for Combinatorial Optimization Problems
  8. 2024Leader Reward for POMO-Based Neural Combinatorial Optimization