Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization

2022/05/26 by Min-Su Kim, Junyoung Park, Kim, Minsu +3 · 15 citations
Computer Science · Engineering · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Metaheuristic Optimization Algorithms Research #Vehicle Routing Optimization Methods

paper · pdf · doi:10.48550/arxiv.2205.13209

openalex publication_date 2022/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• TSP with Predictions: Heatmap to Tour with Provable Guarantees
• ARC: Leveraging Compositional Representations for Cross-Problem Learning on VRPs
• Bridging Synthetic and Real Routing Problems via LLM-Guided Instance Generation and Progressive Adaptation
• A Unified Deep Reinforcement Learning Approach for Close Enough Traveling Salesman Problem
• Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP
• Multi-Action Self-Improvement for Neural Combinatorial Optimization
• Black-Box Combinatorial Optimization with Order-Invariant Reinforcement Learning
• VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems
• URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization
• AutoPref: Automatic Discovery of Task-Specific Preference Objectives for Neural Combinatorial Optimization
• Recurrent State Encoders for Efficient Neural Combinatorial Optimization
• Lifelong Learner: Discovering Versatile Neural Solvers for Vehicle Routing Problems
• On Distributional Dependent Performance of Classical and Neural Routing Solvers
• Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem
• LRM-1B: Towards Large Routing Model

Related

• How Good Is Neural Combinatorial Optimization? A Systematic Evaluation on the Traveling Salesman Problem
• POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
• Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimization
• Leader Reward for POMO-Based Neural Combinatorial Optimization
• Neural Solver Selection for Combinatorial Optimization