Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem

In this work we focus on the well-known Euclidean Traveling Salesperson\nProblem (TSP) and two highly competitive inexact heuristic TSP solvers, EAX and\nLKH, in the context of per-instance algorithm selection (AS). We evolve\ninstances with 1,000 nodes where the solvers show strongly different\nperformance profiles. These instances serve as a basis for an exploratory study\non the identification of well-discriminating problem characteristics\n(features). Our results in a nutshell: we show that even though (1) promising\nfeatures exist, (2) these are in line with previous results from the\nliterature, and (3) models trained with these features are more accurate than\nmodels adopting sophisticated feature selection methods, the advantage is not\nclose to the virtual best solver in terms of penalized average runtime and so\nis the performance gain over the single best solver. However, we show that a\nfeature-free deep neural network based approach solely based on visual\nrepresentation of the instances already matches classical AS model results and\nthus shows huge potential for future studies.\n