Timezone: »

 
Poster
Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization
Minsu Kim · Junyoung Park · Jinkyoo Park

Thu Dec 01 02:00 PM -- 04:00 PM (PST) @ Hall J #707
in Poster Session 6 »
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$\times$ faster speed. Our source code is available at https://github.com/alstn12088/Sym-NCO.
Keywords: Combinatorial Optimization · Reinforcement Learning · Symmetricity · Equivariant
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Minsu Kim (Korea Advanced Institute of Science and Technology)
Junyoung Park (KAIST/Stanford)
Jinkyoo Park (KAIST)

More from the Same Authors