Application of Machine Learning to Algorithm Selection for TSP

The Travelling Salesman Problem (TSP) has been extensively studied in the literature and various solvers are available. However, none of the state-of-the-art solvers for TSP outperforms the others in all problem instances within a given time limit. Therefore, the prediction of the best performing algorithm can save computational resources and optimise the results. In this paper, the TSP is studied in context of automated algorithm selection. Our aim is to identify the relevant features of problem instances and tackle this scenario as a machine learning task. We extend the set of existing features in the literature and propose several novel features to better characterise the problem. The contribution of the new features is statistically analysed and experiments show that adding our new features improves the prediction accuracy. We identified that our features based on kNN graph transformation are especially helpful. To create the training datasets, two state-of-the-art (meta-) heuristic algorithms are systematically evaluated on more than 2000 problems. Overall, we show that our prediction can be substantially more accurate than simple preference of an algorithm with the best performance for a majority of problem instances.