mlsanityData to 7 Oct 2026

Neural Combinatorial Optimization with Reinforcement Learning

arXiv 1611.09940 ↗First posted 29 Nov 2016cs.AI cs.LG stat.MLcited by 600

Not on the map. Why?

Abstract (arXiv)

This paper presents a framework to tackle combinatorial optimization problems using neural networks and reinforcement learning. We focus on the traveling salesman problem (TSP) and train a recurrent network that, given a set of city coordinates, predicts a distribution over different city permutations. Using negative tour length as the reward signal, we optimize the parameters of the recurrent network using a policy gradient method. We compare learning the network parameters on a set of training graphs against learning them on individual test graphs. Despite the computational expense, without much engineering and heuristic designing, Neural Combinatorial Optimization achieves close to optimal results on 2D Euclidean graphs with up to 100 nodes. Applied to the KnapSack, another NP-hard problem, the same method obtains optimal solutions for instances with up to 200 items.

Key facts. Cited by 600 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 Nov 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 108; 2022: 92; 2023: 92; 2024: 107; 2025: 104; 2026: 97.

600 papers.

Sort:

By area:

  1. 2024Gemma 2: Improving Open Language Models at a Practical Sizecited by 1,928
  2. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
  3. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  4. 2024Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Modelcited by 258
  5. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
  6. 2024PaliGemma 2: A Family of Versatile VLMs for Transfercited by 204
  7. 2021End-to-End Constrained Optimization Learning: A Surveycited by 154
  8. 2021Graph Learning: A Surveycited by 140
  9. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 140
  10. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  11. 2025Training Agents Inside of Scalable World Modelscited by 122
  12. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 118
38 more
  1. 2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
  2. 2021LambdaNetworks: Modeling Long-Range Interactions Without Attentioncited by 107
  3. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 107
  4. 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 102
  5. 2025Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Designcited by 100
  6. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 99
  7. 2021Symbolic Regression via Neural-Guided Genetic Programming Population Seedingcited by 97
  8. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  9. 2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 89
  10. 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
  11. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  12. 2021Size-Invariant Graph Representations for Graph Classification Extrapolationscited by 82
  13. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 82
  14. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  15. 2023BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimizationcited by 80
  16. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 77
  17. 2021Machine Learning for Electronic Design Automation: A Surveycited by 71
  18. 2021Graph Neural Network Guided Local Search for the Traveling Salesperson Problemcited by 70
  19. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 70
  20. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  21. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 68
  22. 2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 61
  23. 2023Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policycited by 61
  24. 2021The Transformer Network for the Traveling Salesman Problemcited by 59
  25. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  26. 2021Ordering-Based Causal Discovery with Reinforcement Learningcited by 55
  27. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 54
  28. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  29. 2021CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraintscited by 49
  30. 2023Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problemcited by 49
  31. 2024Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalizationcited by 49
  32. 2021Learning to Select Cuts for Efficient Mixed-Integer Programmingcited by 48
  33. 2023Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Modelcited by 44
  34. 2023H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problemcited by 43
  35. 2024INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformercited by 43
  36. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 43
  37. 2021Learning a Large Neighborhood Search Algorithm for Mixed Integer Programscited by 41
  38. 2023Combinatorial Optimization with Policy Adaptation using Latent Space Searchcited by 41

50 most cited of 600 All 600 (JSON)