Towards Feature-free TSP Solver Selection: A Deep Learning Approach

It is widely recognized that for the traveling salesman problem (TSP), there exists no universal best solver for all problem instances. This observation has greatly facilitated the research on Algorithm Selection (AS), which seeks to identify the solver best suited for each TSP instance. Such segregation usually relies on a prior representation step, in which problem instances are first represented by carefully established problem features. However, the creation of good features is non-trivial, typically requiring considerable domain knowledge and human effort. To alleviate this issue, this paper proposes a deep learning framework, named CTAS, for TSP solver selection. Specifically, CTAS exploits deep convolutional neural networks (CNN) to automatically extract informative features from TSP instances and utilizes data augmentation to handle the scarcity of labeled instances. Extensive experiments are conducted on a challenging TSP benchmark with 6, 000 instances, which is the largest benchmark ever considered in this area. CTAS achieves over 2 × speedup of the average running time, compared with the single best solver. More importantly, CTAS is the first feature-free approach that notably outperforms classical AS models, showing huge potential of applying deep learning to AS tasks.