How Good is Neural Combinatorial Optimization? A Systematic Evaluation on the Traveling Salesman Problem

Shengcai LIU, Yu ZHANG, Ke TANG, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

7 Citations (Scopus)

Abstract

Traditional solvers for tackling combinatorial optimization (CO) problems are usually designed by human experts. Recently, there has been a surge of interest in utilizing deep learning, especially deep reinforcement learning, to automatically learn effective solvers for CO. The resultant new paradigm is termed neural combinatorial optimization (NCO). However, the advantages and disadvantages of NCO relative to other approaches have not been empirically or theoretically well studied. This work presents a comprehensive comparative study of NCO solvers and alternative solvers. Specifically, taking the traveling salesman problem as the testbed problem, the performance of the solvers is assessed in five aspects, i.e., effectiveness, efficiency, stability, scalability, and generalization ability. Our results show that the solvers learned by NCO approaches, in general, still fall short of traditional solvers in nearly all these aspects. A potential benefit of NCO solvers would be their superior time and energy efficiency for small-size problem instances when sufficient training instances are available. Hopefully, this work would help with a better understanding of the strengths and weaknesses of NCO and provide a comprehensive evaluation protocol for further benchmarking NCO approaches in comparison to other approaches. © 2005-2012 IEEE.
Original languageEnglish
Pages (from-to)14-28
Number of pages15
JournalIEEE Computational Intelligence Magazine
Volume18
Issue number3
Early online date19 Jul 2023
DOIs
Publication statusPublished - Aug 2023
Externally publishedYes

Bibliographical note

This work was supported in part by the National Key Research and Development Program of China under Grant 2022YFA1004102, in part by the National Natural Science Foundation of China under Grant 62250710682, and in part by the National Natural Science Foundation of China under Grant 62272210.

Fingerprint

Dive into the research topics of 'How Good is Neural Combinatorial Optimization? A Systematic Evaluation on the Traveling Salesman Problem'. Together they form a unique fingerprint.

Cite this