mlsanityData to 7 Oct 2026

ASP: Learn a Universal Neural Solver!

arXiv 2303.00466 ↗First posted 1 Mar 2023cs.LG cs.AI math.OCcited by 27

Not on the map. Why?

Abstract (arXiv)

Applying machine learning to combinatorial optimization problems has the potential to improve both efficiency and accuracy. However, existing learning-based solvers often struggle with generalization when faced with changes in problem distributions and scales. In this paper, we propose a new approach called ASP: Adaptive Staircase Policy Space Response Oracle to address these generalization issues and learn a universal neural solver. ASP consists of two components: Distributional Exploration, which enhances the solver's ability to handle unknown distributions using Policy Space Response Oracles, and Persistent Scale Adaption, which improves scalability through curriculum learning. We have tested ASP on several challenging COPs, including the traveling salesman problem, the vehicle routing problem, and the prize collecting TSP, as well as the real-world instances from TSPLib and CVRPLib. Our results show that even with the same model size and weak training signal, ASP can help neural solvers explore and adapt to unseen distributions and varying scales, achieving superior performance. In particular, compared with the same neural solvers under a standard training pipeline, ASP produces a remarkable decrease in terms of the optimality gap with 90.9% and 47.43% on generated instances and real-world instances for TSP, and a decrease of 19% and 45.57% for CVRP.

Key facts. Cited by 27 papers in the map (data through 7 Oct 2026). Builds on 40 of its 67 references that are in the map. First posted on arXiv 1 Mar 2023.

Builds on

40 of 67 references.

References · 40

  1. 2017Attention Is All You Needcited by 59,932
  2. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  3. 2017Graph Attention Networkscited by 8,854
  4. 2016Density estimation using Real NVPcited by 2,029
  5. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  6. 2017Visualizing the Loss Landscape of Neural Netscited by 1,126
  7. 2015Pointer Networkscited by 882
  8. 2018Attention, Learn to Solve Routing Problems!cited by 646
  9. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  10. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  11. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  12. 2017Sharp Minima Can Generalize For Deep Netscited by 462
28 more
  1. 2016Entropy-SGD: Biasing Gradient Descent Into Wide Valleyscited by 357
  2. 2020Curriculum Learning for Reinforcement Learning Domains: A Framework and Surveycited by 350
  3. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 341
  4. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  5. 2017A Unified Game-Theoretic Approach to Multiagent Reinforcement Learningcited by 265
  6. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  7. 2019Competence-based Curriculum Learning for Neural Machine Translationcited by 201
  8. 2017Reverse Curriculum Generation for Reinforcement Learningcited by 185
  9. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 183
  10. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 162
  11. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 161
  12. 2020Automatic Curriculum Learning For Deep RL: A Short Surveycited by 141
  13. 2022Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learningcited by 129
  14. 2018CurriculumNet: Weakly Supervised Learning from Large-Scale Web Imagescited by 126
  15. 2020Stabilizing Differentiable Architecture Search via Perturbation-based Regularizationcited by 102
  16. 2020Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problemscited by 100
  17. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  18. 2014Curriculum Learning of Multiple Taskscited by 65
  19. 2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 61
  20. 2019Simple and Effective Curriculum Pointer-Generator Networks for Reading Comprehension over Long Narrativescited by 59
  21. 2021Modelling Behavioural Diversity for Learning in Open-Ended Gamescited by 39
  22. 2022Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculumcited by 27
  23. 2022ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regretcited by 24
  24. 2020Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimizationcited by 19
  25. 2021A Game-Theoretic Approach for Improving Generalization Ability of TSP Solverscited by 14
  26. 2022Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Gamescited by 11
  27. 2022Curriculum-based Asymmetric Multi-task Reinforcement Learningcited by 7
  28. 2020Learning Robust Algorithms for Online Allocation Problems Using Adversarial Trainingcited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 11; 2025: 8; 2026: 5.

27 papers.

Sort:

By area:

  1. 2024ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolutioncited by 266
  2. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  3. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  4. 2025Large Language Models as End-to-end Combinatorial Optimization Solverscited by 27
  5. 2024A Survey on Self-play Methods in Reinforcement Learningcited by 26
  6. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  7. 2025Generative Models in Decision Making: A Surveycited by 14
  8. 2025BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimizationcited by 14
  9. 2023Promoting Generalization for Exact Solvers via Adversarial Instance Augmentationcited by 12
  10. 2025Preference Optimization for Combinatorial Optimization Problemscited by 11
  11. 2024Policy Space Response Oracles: A Surveycited by 10
  12. 2024PRANCE: Joint Token-Optimization and Structural Channel-Pruning for Adaptive ViT Inferencecited by 10
15 more
  1. 2023Efficient Training of Multi-task Neural Solver for Combinatorial Optimizationcited by 6
  2. 2024Unveiling and Mitigating Generalized Biases of DNNs through the Intrinsic Dimensions of Perceptual Manifoldscited by 6
  3. 2024Neural Solver Selection for Combinatorial Optimizationcited by 5
  4. 2026Survey on Neural Routing Solverscited by 4
  5. 2024Towards Principled Task Grouping for Multi-Task Learningcited by 3
  6. 2024Beyond the Heatmap: A Rigorous Evaluation of Component Impact in MCTS-Based TSP Solverscited by 3
  7. 2023An Edge-Aware Graph Autoencoder Trained on Scale-Imbalanced Data for Traveling Salesman Problemscited by 2
  8. 2026Game-Theoretic Co-Evolution for LLM-Based Heuristic Discoverycited by 2
  9. 2025Boosting Cross-problem Generalization in Diffusion-Based Neural Combinatorial Solver via Inference Time Adaptationcited by 1
  10. 2025Lifelong Learning with Behavior Consolidation for Vehicle Routingcited by 1
  11. 2025Empowering Targeted Neighborhood Search via Hyper Tour for Large-Scale TSPcited by 1
  12. 2026Learning with Foresight: Enhancing Neural Routing Policy via Multi-Node Lookahead Predictioncited by 1
  13. 2025Multi-Dimensional AGV Path Planning in 3D Warehouses Using Ant Colony Optimization and Advanced Neural Networkscited by 0
  14. 2026Keep Rehearsing and Refining: Lifelong Learning Vehicle Routing under Continually Drifting Taskscited by 0
  15. 2026LaT: LLM-as-Trainer for Multi-Task Vehicle Routing Solverscited by 0