# PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 40 of its 66 references that are in the map.
- First posted on arXiv 21 Feb 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (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)
- [Dynamics-Aware Unsupervised Discovery of Skills](https://mlsanity.com/paper/1907.01657/) (2019)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [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)
- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood](https://mlsanity.com/paper/2012.10384/) (2020)
- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021)
- [Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning](https://mlsanity.com/paper/2004.01608/) (2020)
- [Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2012.10638/) (2020)
- [Efficient Active Search for Combinatorial Optimization Problems](https://mlsanity.com/paper/2106.05126/) (2021)
- [Celebrating Diversity in Shared Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2106.02195/) (2021)
- [Deep Policy Dynamic Programming for Vehicle Routing Problems](https://mlsanity.com/paper/2102.11756/) (2021)
- [Matrix Encoding Networks for Neural Combinatorial Optimization](https://mlsanity.com/paper/2106.11113/) (2021)
- [Learning Collaborative Policies to Solve NP-hard Routing Problems](https://mlsanity.com/paper/2110.13987/) (2021)
- [Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis](https://mlsanity.com/paper/1805.04276/) (2018)
- [Simulation-guided Beam Search for Neural Combinatorial Optimization](https://mlsanity.com/paper/2207.06190/) (2022)
- [BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization](https://mlsanity.com/paper/2301.03313/) (2023)
- [Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt](https://mlsanity.com/paper/2310.18264/) (2023)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)

## Built on by (most cited first, 30 of 35)

- [MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts](https://mlsanity.com/paper/2405.01029/) (2024)
- [RouteFinder: Towards Foundation Models for Vehicle Routing Problems](https://mlsanity.com/paper/2406.15007/) (2024)
- [Rethinking Light Decoder-based Solvers for Vehicle Routing Problems](https://mlsanity.com/paper/2503.00753/) (2025)
- [Learning to Handle Complex Constraints for Vehicle Routing Problems](https://mlsanity.com/paper/2410.21066/) (2024)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Neural Deconstruction Search for Vehicle Routing Problems](https://mlsanity.com/paper/2501.03715/) (2025)
- [Learning to Insert for Constructive Neural Vehicle Routing Solver](https://mlsanity.com/paper/2505.13904/) (2025)
- [Collaboration! Towards Robust Neural Methods for Routing Problems](https://mlsanity.com/paper/2410.04968/) (2024)
- [VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems](https://mlsanity.com/paper/2510.07073/) (2025)
- [Memory-Enhanced Neural Solvers for Routing Problems](https://mlsanity.com/paper/2406.16424/) (2024)
- [Learning Multiple Initial Solutions to Optimization Problems](https://mlsanity.com/paper/2411.02158/) (2024)
- [Survey on Neural Routing Solvers](https://mlsanity.com/paper/2602.21761/) (2026)
- [Bridging Synthetic and Real Routing Problems via LLM-Guided Instance Generation and Progressive Adaptation](https://mlsanity.com/paper/2511.10233/) (2025)
- [Towards Efficient Constraint Handling in Neural Solvers for Routing Problems](https://mlsanity.com/paper/2602.16012/) (2026)
- [Learning to Solve the Min-Max Mixed-Shelves Picker-Routing Problem via Hierarchical and Parallel Decoding](https://mlsanity.com/paper/2502.10233/) (2025)
- [Breaking the Performance Ceiling in Reinforcement Learning requires Inference Strategies](https://mlsanity.com/paper/2505.21236/) (2025)
- [Chain-of-Context Learning: Dynamic Constraint Understanding for Multi-Task VRPs](https://mlsanity.com/paper/2603.01667/) (2026)
- [USPR: Learning a Unified Solver for Profiled Routing](https://mlsanity.com/paper/2505.05119/) (2025)
- [Recurrent State Encoders for Efficient Neural Combinatorial Optimization](https://mlsanity.com/paper/2509.05084/) (2025)
- [Speed is Confidence](https://mlsanity.com/paper/2601.19085/) (2026)
- [Efficient Decoder Scaling Strategy for Neural Routing Solvers](https://mlsanity.com/paper/2603.00430/) (2026)
- [Learning with Foresight: Enhancing Neural Routing Policy via Multi-Node Lookahead Prediction](https://mlsanity.com/paper/2605.19975/) (2026)
- [Latent Guided Sampling for Combinatorial Optimization](https://mlsanity.com/paper/2506.03672/) (2025)
- [Synergizing Reinforcement Learning and Genetic Algorithms for Neural Combinatorial Optimization](https://mlsanity.com/paper/2506.09404/) (2025)
- [On Distributional Dependent Performance of Classical and Neural Routing Solvers](https://mlsanity.com/paper/2508.02510/) (2025)
- [Multi-Action Self-Improvement for Neural Combinatorial Optimization](https://mlsanity.com/paper/2510.12273/) (2025)
- [Enabling Population-Based Architectures for Neural Combinatorial Optimization](https://mlsanity.com/paper/2601.08696/) (2026)
- [Learning to Solve Orienteering Problem with Time Windows and Variable Profits](https://mlsanity.com/paper/2603.06260/) (2026)
- [Enhancing Cross-Problem Vehicle Routing via Federated Learning](https://mlsanity.com/paper/2604.10652/) (2026)
- [Learning to Solve the Quadratic Assignment Problem with Warm-Started MCMC Finetuning](https://mlsanity.com/paper/2604.20109/) (2026)

## Abstract (arXiv)

Reinforcement learning-based methods for constructing solutions to combinatorial optimization problems are rapidly approaching the performance of human-designed algorithms. To further narrow the gap, learning-based approaches must efficiently explore the solution space during the search process. Recent approaches artificially increase exploration by enforcing diverse solution generation through handcrafted rules, however, these rules can impair solution quality and are difficult to design for more complex problems. In this paper, we introduce PolyNet, an approach for improving exploration of the solution space by learning complementary solution strategies. In contrast to other works, PolyNet uses only a single-decoder and a training schema that does not enforce diverse solution generation through handcrafted rules. We evaluate PolyNet on four combinatorial optimization problems and observe that the implicit diversity mechanism allows PolyNet to find better solutions than approaches that explicitly enforce diverse solution generation.