Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization
This work addresses the problem of enhancing neural combinatorial optimization methods for researchers and practitioners by providing a more generalizable approach, though it is incremental as it builds on existing DRL-NCO frameworks.
The paper tackles the challenge of improving generalization in deep reinforcement learning for combinatorial optimization by introducing Sym-NCO, a training scheme that leverages symmetricities like rotational and reflectional invariance, resulting in performance gains across four tasks, including outperforming a conventional solver in prize collecting TSP at 240 times faster speed.
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.