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 without supervised labels
attained from the verified solver. This paper presents a novel training scheme,
Sym-NCO, that achieves significant performance increments to existing DRL-NCO
methods. Sym-NCO is a regularizer-based training scheme that leverages
universal symmetricities in various CO problems and solutions. Imposing
symmetricities such as rotational and reflectional invariance can greatly
improve generalization capability of DRL-NCO as symmetricities are invariant
features shared by certain CO tasks. Our experimental results verify that our
Sym-NCO greatly improves the performance of DRL-NCO methods in four CO tasks,
including traveling salesman problem (TSP), capacitated vehicle routing problem
(CVRP), prize collecting TSP (PCTSP), and orienteering problem (OP), without
employing problem-specific techniques. 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 times faster speed.