# ASP: Learn a Universal Neural Solver!

arXiv: https://arxiv.org/abs/2303.00466 · HTML: https://mlsanity.com/paper/2303.00466/

## Key facts

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

## Builds on (most cited first, 30 of 40)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Density estimation using Real NVP](https://mlsanity.com/paper/1605.08803/) (2016)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Visualizing the Loss Landscape of Neural Nets](https://mlsanity.com/paper/1712.09913/) (2017)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Sharp Minima Can Generalize For Deep Nets](https://mlsanity.com/paper/1703.04933/) (2017)
- [Curriculum Learning for Reinforcement Learning Domains: A Framework and Survey](https://mlsanity.com/paper/2003.04960/) (2020)
- [Entropy-SGD: Biasing Gradient Descent Into Wide Valleys](https://mlsanity.com/paper/1611.01838/) (2016)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Competence-based Curriculum Learning for Neural Machine Translation](https://mlsanity.com/paper/1903.09848/) (2019)
- [Reverse Curriculum Generation for Reinforcement Learning](https://mlsanity.com/paper/1707.05300/) (2017)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Automatic Curriculum Learning For Deep RL: A Short Survey](https://mlsanity.com/paper/2003.04664/) (2020)
- [Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning](https://mlsanity.com/paper/2206.15378/) (2022)
- [CurriculumNet: Weakly Supervised Learning from Large-Scale Web Images](https://mlsanity.com/paper/1808.01097/) (2018)
- [Stabilizing Differentiable Architecture Search via Perturbation-based Regularization](https://mlsanity.com/paper/2002.05283/) (2020)
- [Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2012.10638/) (2020)
- [Deep Policy Dynamic Programming for Vehicle Routing Problems](https://mlsanity.com/paper/2102.11756/) (2021)
- [Curriculum Learning of Multiple Tasks](https://mlsanity.com/paper/1412.1353/) (2014)

## Built on by (most cited first, 27 of 27)

- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts](https://mlsanity.com/paper/2405.01029/) (2024)
- [Learning to Handle Complex Constraints for Vehicle Routing Problems](https://mlsanity.com/paper/2410.21066/) (2024)
- [Large Language Models as End-to-end Combinatorial Optimization Solvers](https://mlsanity.com/paper/2509.16865/) (2025)
- [A Survey on Self-play Methods in Reinforcement Learning](https://mlsanity.com/paper/2408.01072/) (2024)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Generative Models in Decision Making: A Survey](https://mlsanity.com/paper/2502.17100/) (2025)
- [BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization](https://mlsanity.com/paper/2503.07580/) (2025)
- [Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation](https://mlsanity.com/paper/2310.14161/) (2023)
- [Preference Optimization for Combinatorial Optimization Problems](https://mlsanity.com/paper/2505.08735/) (2025)
- [Policy Space Response Oracles: A Survey](https://mlsanity.com/paper/2403.02227/) (2024)
- [PRANCE: Joint Token-Optimization and Structural Channel-Pruning for Adaptive ViT Inference](https://mlsanity.com/paper/2407.05010/) (2024)
- [Efficient Training of Multi-task Neural Solver for Combinatorial Optimization](https://mlsanity.com/paper/2305.06361/) (2023)
- [Unveiling and Mitigating Generalized Biases of DNNs through the Intrinsic Dimensions of Perceptual Manifolds](https://mlsanity.com/paper/2404.13859/) (2024)
- [Neural Solver Selection for Combinatorial Optimization](https://mlsanity.com/paper/2410.09693/) (2024)
- [Survey on Neural Routing Solvers](https://mlsanity.com/paper/2602.21761/) (2026)
- [Towards Principled Task Grouping for Multi-Task Learning](https://mlsanity.com/paper/2402.15328/) (2024)
- [Beyond the Heatmap: A Rigorous Evaluation of Component Impact in MCTS-Based TSP Solvers](https://mlsanity.com/paper/2411.09238/) (2024)
- [An Edge-Aware Graph Autoencoder Trained on Scale-Imbalanced Data for Traveling Salesman Problems](https://mlsanity.com/paper/2310.06543/) (2023)
- [Game-Theoretic Co-Evolution for LLM-Based Heuristic Discovery](https://mlsanity.com/paper/2601.22896/) (2026)
- [Boosting Cross-problem Generalization in Diffusion-Based Neural Combinatorial Solver via Inference Time Adaptation](https://mlsanity.com/paper/2502.12188/) (2025)
- [Lifelong Learning with Behavior Consolidation for Vehicle Routing](https://mlsanity.com/paper/2509.21765/) (2025)
- [Empowering Targeted Neighborhood Search via Hyper Tour for Large-Scale TSP](https://mlsanity.com/paper/2510.20169/) (2025)
- [Learning with Foresight: Enhancing Neural Routing Policy via Multi-Node Lookahead Prediction](https://mlsanity.com/paper/2605.19975/) (2026)
- [Multi-Dimensional AGV Path Planning in 3D Warehouses Using Ant Colony Optimization and Advanced Neural Networks](https://mlsanity.com/paper/2504.01985/) (2025)
- [Keep Rehearsing and Refining: Lifelong Learning Vehicle Routing under Continually Drifting Tasks](https://mlsanity.com/paper/2601.22509/) (2026)
- [LaT: LLM-as-Trainer for Multi-Task Vehicle Routing Solvers](https://mlsanity.com/paper/2607.17708/) (2026)

## 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.