Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization
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.
Code (1)
Tasks
Combinatorial OptimizationDeep Reinforcement LearningTraveling Salesman ProblemMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
DevFormer: A Symmetric Transformer for Context-Aware Device Placement
In this paper, we present DevFormer, a novel transformer-based architecture for addressing the complex and computationally demanding problem of hardware design optimization. Despite the demonstrated efficacy of transform…
Combinatorial OptimizationMeta-LearningStructure Learning of Markov Random Fields through Grow-Shrink Maximum Pseudolikelihood Estimation
Learning the structure of Markov random fields (MRFs) plays an important role in multivariate analysis. The importance has been increasing with the recent rise of statistical relational models since the MRF serves as a b…
End-to-End Constrained Optimization Learning: A Survey
This paper surveys the recent attempts at leveraging machine learning to solve constrained optimization problems. It focuses on surveying the work on integrating combinatorial solvers and optimization methods with machin…
BIG-bench Machine LearningHybrid Machine LearningSurveyMachine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon
This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems. Given the hard nature of these prob…
BIG-bench Machine LearningCombinatorial OptimizationCombinatorial Optimization via LLM-driven Iterated Fine-tuning
We present a novel way to integrate flexible, context-dependent constraints into combinatorial optimization by leveraging Large Language Models (LLMs) alongside traditional algorithms. Although LLMs excel at interpreting…
Combinatorial Optimizationglobal-optimizationScheduling