mlsanityData to 14 Oct 2026

Simulation-guided Beam Search for Neural Combinatorial Optimization

arXiv 2207.06190 ↗First posted 13 Jul 2022cs.LG cs.AIcited by 84

Not on the map. Why?

Abstract (arXiv)

Neural approaches for combinatorial optimization (CO) equip a learning mechanism to discover powerful heuristics for solving complex real-world problems. While neural approaches capable of high-quality solutions in a single shot are emerging, state-of-the-art approaches are often unable to take full advantage of the solving time available to them. In contrast, hand-crafted heuristics perform highly effective search well and exploit the computation time given to them, but contain heuristics that are difficult to adapt to a dataset being solved. With the goal of providing a powerful search procedure to neural CO approaches, we propose simulation-guided beam search (SGBS), which examines candidate solutions within a fixed-width tree search that both a neural net-learned policy and a simulation (rollout) identify as promising. We further hybridize SGBS with efficient active search (EAS), where SGBS enhances the quality of solutions backpropagated in EAS, and EAS improves the quality of the policy used in SGBS. We evaluate our methods on well-known CO benchmarks and show that SGBS significantly improves the quality of the solutions found under reasonable runtime assumptions.

Key facts. Cited by 84 papers in the map (data through 14 Oct 2026). Builds on 34 of its 64 references that are in the map. First posted on arXiv 13 Jul 2022.

Builds on

34 of 64 references.

References · 34

  1. 2017On Calibration of Modern Neural Networkscited by 4,960
  2. 2015Pointer Networkscited by 895
  3. 2018Attention, Learn to Solve Routing Problems!cited by 656
  4. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  5. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  6. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  7. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 348
  8. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 333
  9. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 269
  10. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 185
  11. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 183
  12. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 164
22 more
  1. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 162
  2. 2020Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learningcited by 140
  3. 2020Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhoodcited by 125
  4. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  5. 2021Learning to Delegate for Large-scale Vehicle Routingcited by 109
  6. 2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
  7. 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 103
  8. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  9. 2020Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problemscited by 100
  10. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 100
  11. 2020Learning the Travelling Salesperson Problem Requires Rethinking Generalizationcited by 98
  12. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  13. 2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 91
  14. 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
  15. 2019Exploratory Combinatorial Optimization with Reinforcement Learningcited by 82
  16. 2020Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routingcited by 61
  17. 2021On Joint Learning for Solving Placement and Routing in Chip Designcited by 44
  18. 2022Efficient Neural Neighborhood Search for Pickup and Delivery Problemscited by 29
  19. 2019Solving NP-Hard Problems on Graphs with Extended AlphaGo Zerocited by 23
  20. 2017Deep Learning Assisted Heuristic Tree Search for the Container Pre-marshalling Problemcited by 18
  21. 2018Learning Beam Search Policies via Imitation Learningcited by 9
  22. 2020Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problemscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 15; 2024: 30; 2025: 23; 2026: 14.

84 papers.

Sort:

By area:

  1. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 221
  2. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 142
  3. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 85
  4. 2023BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimizationcited by 82
  5. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  6. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 78
  7. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 71
  8. 2022Winner Takes It All: Training Performant RL Populations for Combinatorial Optimizationcited by 58
  9. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 55
  10. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  11. 2024Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalizationcited by 50
  12. 2024INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformercited by 44
38 more
  1. 2024GOAL: A Generalist Combinatorial Optimization Agent Learnercited by 42
  2. 2023Combinatorial Optimization with Policy Adaptation using Latent Space Searchcited by 41
  3. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimizationcited by 35
  4. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvementcited by 34
  5. 2024Self-Improved Learning for Scalable Neural Combinatorial Optimizationcited by 29
  6. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  7. 2024Cross-Problem Learning for Solving Vehicle Routing Problemscited by 24
  8. 2023Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimizationcited by 23
  9. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  10. 2022Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Schedulingcited by 20
  11. 2023Equity-Transformer: Solving NP-hard Min-Max Routing Problems as Sequential Generation with Equity Contextcited by 16
  12. 2024Distance-aware Attention Reshaping: Enhance Generalization of Neural Solver for Large-scale Vehicle Routing Problemscited by 15
  13. 2024Graph Neural Networks for Job Shop Scheduling Problems: A Surveycited by 15
  14. 2025Neural Deconstruction Search for Vehicle Routing Problemscited by 15
  15. 2025On Almost Surely Safe Alignment of Large Language Models at Inference-Timecited by 14
  16. 2024DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problemscited by 11
  17. 2023Adjustable Robust Reinforcement Learning for Online 3D Bin Packingcited by 10
  18. 2024Hierarchical Neural Constructive Solver for Real-world TSP Scenarioscited by 10
  19. 2025Adversarial Generative Flow Network for Solving Vehicle Routing Problemscited by 10
  20. 2025Learning to Insert for Constructive Neural Vehicle Routing Solvercited by 10
  21. 2024Instance-Conditioned Adaptation for Large-scale Generalization of Neural Routing Solvercited by 9
  22. 2023Deep reinforcement learning for machine scheduling: Methodology, the state-of-the-art, and future directionscited by 8
  23. 2024Bridging Large Language Models and Optimization: A Unified Framework for Text-attributed Combinatorial Optimizationcited by 8
  24. 2025Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degreescited by 8
  25. 2026RADAR: Learning to Route with Asymmetry-aware DistAnce Representationscited by 8
  26. 2023Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimizationcited by 7
  27. 2024Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and Morecited by 7
  28. 2023Too Big, so Fail? -- Enabling Neural Construction Methods to Solve Large-Scale Routing Problemscited by 6
  29. 2023Routing Arena: A Benchmark Suite for Neural Routing Solverscited by 5
  30. 2024Moco: A Learnable Meta Optimizer for Combinatorial Optimizationcited by 5
  31. 2024Leader Reward for POMO-Based Neural Combinatorial Optimizationcited by 5
  32. 2025Neural Genetic Search in Discrete Spacescited by 5
  33. 2024Memory-Enhanced Neural Solvers for Routing Problemscited by 4
  34. 2024Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimizationcited by 4
  35. 2026Survey on Neural Routing Solverscited by 4
  36. 2024Continuous Parallel Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problemscited by 3
  37. 2024Learning Heuristics for Transit Network Design and Improvement with Deep Reinforcement Learningcited by 3
  38. 2024MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimizationcited by 3

50 most cited of 84 All 84 (JSON)