Predicting the Empirical Hardness of Metric TSP Instances

In this work, we propose to classify the empirical hardness of metric Travelling Salesman Problem (TSP) instances by using four features that depend only on the distribution of values in the cost matrix. The first three features are the standard deviation, the skewness, and the Gini index of the cost coefficients. The fourth feature is based on a new statistic, called the tight triangle inequality index, which gives the percentage over all possible triangle inequalities in the cost matrix that are satisfied with equality. As a dataset, we used over 45000 instances, both collected from the literature and randomly generated, which we labeled as easy or hard by using the number of branch and bound nodes of Concorde. After computing the four features for all the instances in the training set, we designed a decision tree that predicts the empirical hardness of instances in the test set with high values of the Matthew Correlation Coefficient prediction score.