mlsanityData to 7 Oct 2026

POMO: Policy Optimization with Multiple Optima for Reinforcement Learning

arXiv 2010.16011 ↗First posted 30 Oct 2020cs.LGcited by 341

Not on the map. Why?

Abstract (arXiv)

In neural combinatorial optimization (CO), reinforcement learning (RL) can turn a deep neural net into a fast, powerful heuristic solver of NP-hard problems. This approach has a great potential in practical applications because it allows near-optimal solutions to be found without expert guides armed with substantial domain knowledge. We introduce Policy Optimization with Multiple Optima (POMO), an end-to-end approach for building such a heuristic solver. POMO is applicable to a wide range of CO problems. It is designed to exploit the symmetries in the representation of a CO solution. POMO uses a modified REINFORCE algorithm that forces diverse rollouts towards all optimal solutions. Empirically, the low-variance baseline of POMO makes RL training fast and stable, and it is more resistant to local minima compared to previous approaches. We also introduce a new augmentation-based inference method, which accompanies POMO nicely. We demonstrate the effectiveness of POMO by solving three popular NP-hard problems, namely, traveling salesman (TSP), capacitated vehicle routing (CVRP), and 0-1 knapsack (KP). For all three, our solver based on POMO shows a significant improvement in performance over all recent learned heuristics. In particular, we achieve the optimality gap of 0.14% with TSP100 while reducing inference time by more than an order of magnitude.

Key facts. Cited by 341 papers in the map (data through 7 Oct 2026). First posted on arXiv 30 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 27; 2023: 45; 2024: 63; 2025: 90; 2026: 104.

341 papers.

Sort:

By area:

  1. 2024ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolutioncited by 266
  2. 2024Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Modelcited by 258
  3. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
  4. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 140
  5. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  6. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 118
  7. 2021Learning to Delegate for Large-scale Vehicle Routingcited by 108
  8. 2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
  9. 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 102
  10. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 99
  11. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  12. 2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 89
38 more
  1. 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
  2. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  3. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 82
  4. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  5. 2023BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimizationcited by 80
  6. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 77
  7. 2021Graph Neural Network Guided Local Search for the Traveling Salesperson Problemcited by 70
  8. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 70
  9. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  10. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 68
  11. 2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 61
  12. 2023Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policycited by 61
  13. 2022Winner Takes It All: Training Performant RL Populations for Combinatorial Optimizationcited by 57
  14. 2023Unsupervised Learning for Solving the Travelling Salesman Problemcited by 57
  15. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  16. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 54
  17. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  18. 2023Jumanji: a Diverse Suite of Scalable Reinforcement Learning Environments in JAXcited by 52
  19. 2023Algorithm Evolution Using Large Language Modelcited by 52
  20. 2023Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problemcited by 49
  21. 2024Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalizationcited by 49
  22. 2023H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problemcited by 43
  23. 2024INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformercited by 43
  24. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 43
  25. 2023Combinatorial Optimization with Policy Adaptation using Latent Space Searchcited by 41
  26. 2023Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetscited by 40
  27. 2024GOAL: A Generalist Combinatorial Optimization Agent Learnercited by 39
  28. 2024Genetic-guided GFlowNets for Sample Efficient Molecular Optimizationcited by 36
  29. 2025Rethinking Light Decoder-based Solvers for Vehicle Routing Problemscited by 36
  30. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimizationcited by 35
  31. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  32. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvementcited by 32
  33. 2022Learning to Solve Routing Problems via Distributionally Robust Optimizationcited by 31
  34. 2022Efficient Neural Neighborhood Search for Pickup and Delivery Problemscited by 29
  35. 2024Self-Improved Learning for Scalable Neural Combinatorial Optimizationcited by 29
  36. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  37. 2022Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculumcited by 27
  38. 2023ASP: Learn a Universal Neural Solver!cited by 27

50 most cited of 341 All 341 (JSON)