mlsanityData to 14 Oct 2026

Learning to Control Local Search for Combinatorial Optimization

arXiv 2206.13181 ↗First posted 27 Jun 2022cs.LG math.OCcited by 18

Not on the map. Why?

Abstract (arXiv)

Combinatorial optimization problems are encountered in many practical contexts such as logistics and production, but exact solutions are particularly difficult to find and usually NP-hard for considerable problem sizes. To compute approximate solutions, a zoo of generic as well as problem-specific variants of local search is commonly used. However, which variant to apply to which particular problem is difficult to decide even for experts. In this paper we identify three independent algorithmic aspects of such local search algorithms and formalize their sequential selection over an optimization process as Markov Decision Process (MDP). We design a deep graph neural network as policy model for this MDP, yielding a learned controller for local search called NeuroLS. Ample experimental evidence shows that NeuroLS is able to outperform both, well-known general purpose local search controllers from Operations Research as well as latest machine learning-based approaches.

Key facts. Cited by 18 papers in the map (data through 14 Oct 2026). Builds on 33 of its 51 references that are in the map. First posted on arXiv 27 Jun 2022.

Builds on

33 of 51 references.

References · 33

  1. 2017Attention Is All You Needcited by 60,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2016Layer Normalizationcited by 5,669
  4. 2016Gaussian Error Linear Units (GELUs)cited by 3,502
  5. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  6. 2015Pointer Networkscited by 895
  7. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  8. 2018Attention, Learn to Solve Routing Problems!cited by 656
  9. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  10. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  11. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  12. 2018Implicit Quantile Networks for Distributional Reinforcement Learningcited by 369
21 more
  1. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 348
  2. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 333
  3. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 318
  4. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 269
  5. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 236
  6. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 185
  7. 2020Solving Mixed Integer Programs Using Neural Networkscited by 182
  8. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 164
  9. 2020Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learningcited by 140
  10. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  11. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  12. 2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
  13. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  14. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 100
  15. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  16. 2021Graph Neural Network Guided Local Search for the Traveling Salesperson Problemcited by 70
  17. 2021Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learningcited by 52
  18. 2017Solving a New 3D Bin Packing Problem with Deep Reinforcement Learning Methodcited by 31
  19. 2021ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learningcited by 31
  20. 2020Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attentioncited by 29
  21. 2022Supervised Permutation Invariant Networks for Solving the CVRP with Bounded Fleet Sizecited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 4; 2024: 6; 2025: 6; 2026: 2.

18 papers.

Sort:

By area:

  1. 2024Self-Labeling the Job Shop Scheduling Problemcited by 23
  2. 2024Graph Neural Networks for Job Shop Scheduling Problems: A Surveycited by 15
  3. 2025BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimizationcited by 14
  4. 2024Rethinking the Capacity of Graph Neural Networks for Branching Strategycited by 12
  5. 2023Too Big, so Fail? -- Enabling Neural Construction Methods to Solve Large-Scale Routing Problemscited by 6
  6. 2023Routing Arena: A Benchmark Suite for Neural Routing Solverscited by 5
  7. 2024Moco: A Learnable Meta Optimizer for Combinatorial Optimizationcited by 5
  8. 2024Offline reinforcement learning for job-shop scheduling problemscited by 2
  9. 2023Swap-based Deep Reinforcement Learning for Facility Location Problems in Networkscited by 1
  10. 2024Decision Transformer for Enhancing Neural Local Search on the Job Shop Scheduling Problemcited by 1
  11. 2025Recurrent State Encoders for Efficient Neural Combinatorial Optimizationcited by 1
  12. 2023RELS-DQN: A Robust and Efficient Local Search Framework for Combinatorial Optimizationcited by 0
6 more
  1. 2025Discovering new robust local search algorithms with neuro-evolutioncited by 0
  2. 2025Unraveling the Rainbow: can value-based methods schedule?cited by 0
  3. 2025On Distributional Dependent Performance of Classical and Neural Routing Solverscited by 0
  4. 2025Edge-Selector Model Applied for Local Search Neighborhood for Solving Vehicle Routing Problemscited by 0
  5. 2026Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Schedulingcited by 0
  6. 2026TriSearch: Learning to Optimize Triangulations via Bistellar Flipscited by 0