# Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization

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

## Key facts

- Cited by 119 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 66 references that are in the map.
- First posted on arXiv 26 May 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [E(n) Equivariant Graph Neural Networks](https://mlsanity.com/paper/2102.09844/) (2021)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [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)
- [SE(3)-Transformers: 3D Roto-Translation Equivariant Attention Networks](https://mlsanity.com/paper/2006.10503/) (2020)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [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)
- [Permutation Invariant Graph Generation via Score-Based Generative Modeling](https://mlsanity.com/paper/2003.00638/) (2020)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (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)
- [MDP Homomorphic Networks: Group Symmetries in Reinforcement Learning](https://mlsanity.com/paper/2006.16908/) (2020)
- [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)
- [Deep Policy Dynamic Programming for Vehicle Routing Problems](https://mlsanity.com/paper/2102.11756/) (2021)
- [Device Placement Optimization with Reinforcement Learning](https://mlsanity.com/paper/1706.04972/) (2017)
- [Learning Collaborative Policies to Solve NP-hard Routing Problems](https://mlsanity.com/paper/2110.13987/) (2021)
- [Chip Placement with Deep Reinforcement Learning](https://mlsanity.com/paper/2004.10746/) (2020)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Graph Neural Network Guided Local Search for the Traveling Salesperson Problem](https://mlsanity.com/paper/2110.05291/) (2021)
- [Learning What to Defer for Maximum Independent Sets](https://mlsanity.com/paper/2006.09607/) (2020)
- [Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning](https://mlsanity.com/paper/2106.01086/) (2021)
- [Guiding Deep Molecular Optimization with Genetic Exploration](https://mlsanity.com/paper/2007.04897/) (2020)

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

- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time](https://mlsanity.com/paper/2312.08224/) (2023)
- [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)
- [DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization](https://mlsanity.com/paper/2309.14032/) (2023)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts](https://mlsanity.com/paper/2405.01029/) (2024)
- [Towards Omni-generalizable Neural Methods for Vehicle Routing Problems](https://mlsanity.com/paper/2305.19587/) (2023)
- [Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy](https://mlsanity.com/paper/2308.14104/) (2023)
- [Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization](https://mlsanity.com/paper/2210.03475/) (2022)
- [RouteFinder: Towards Foundation Models for Vehicle Routing Problems](https://mlsanity.com/paper/2406.15007/) (2024)
- [Ant Colony Sampling with GFlowNets for Combinatorial Optimization](https://mlsanity.com/paper/2403.07041/) (2024)
- [Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization](https://mlsanity.com/paper/2502.02941/) (2025)
- [GOAL: A Generalist Combinatorial Optimization Agent Learner](https://mlsanity.com/paper/2406.15079/) (2024)
- [Combinatorial Optimization with Policy Adaptation using Latent Space Search](https://mlsanity.com/paper/2311.13569/) (2023)
- [Genetic-guided GFlowNets for Sample Efficient Molecular Optimization](https://mlsanity.com/paper/2402.05961/) (2024)
- [Rethinking Light Decoder-based Solvers for Vehicle Routing Problems](https://mlsanity.com/paper/2503.00753/) (2025)
- [PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization](https://mlsanity.com/paper/2402.14048/) (2024)
- [Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement](https://mlsanity.com/paper/2403.15180/) (2024)
- [Self-Improved Learning for Scalable Neural Combinatorial Optimization](https://mlsanity.com/paper/2403.19561/) (2024)
- [Learning to Handle Complex Constraints for Vehicle Routing Problems](https://mlsanity.com/paper/2410.21066/) (2024)
- [Cross-Problem Learning for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2404.11677/) (2024)
- [Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems](https://mlsanity.com/paper/2406.03503/) (2024)
- [CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention](https://mlsanity.com/paper/2412.00346/) (2024)
- [Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimization](https://mlsanity.com/paper/2306.02688/) (2023)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems](https://mlsanity.com/paper/2405.17272/) (2024)
- [Equity-Transformer: Solving NP-hard Min-Max Routing Problems as Sequential Generation with Equity Context](https://mlsanity.com/paper/2306.02689/) (2023)

## Abstract (arXiv)

Deep reinforcement learning (DRL)-based combinatorial optimization (CO) methods (i.e., DRL-NCO) have shown significant merit over the conventional CO solvers as DRL-NCO is capable of learning CO solvers less relying on problem-specific expert domain knowledge (heuristic method) and supervised labeled data (supervised learning method). This paper presents a novel training scheme, Sym-NCO, which is a regularizer-based training scheme that leverages universal symmetricities in various CO problems and solutions. Leveraging symmetricities such as rotational and reflectional invariance can greatly improve the generalization capability of DRL-NCO because it allows the learned solver to exploit the commonly shared symmetricities in the same CO problem class. Our experimental results verify that our Sym-NCO greatly improves the performance of DRL-NCO methods in four CO tasks, including the traveling salesman problem (TSP), capacitated vehicle routing problem (CVRP), prize collecting TSP (PCTSP), and orienteering problem (OP), without utilizing problem-specific expert domain knowledge. Remarkably, Sym-NCO outperformed not only the existing DRL-NCO methods but also a competitive conventional solver, the iterative local search (ILS), in PCTSP at 240 faster speed. Our source code is available at https://github.com/alstn12088/Sym-NCO.