On the Empirical Scaling of Running Time for Finding Optimal Solutions to the TSP: Supplementary material

by Zongxu Mu, Jérémie Dubois-Lacoste, Holger H. Hoos, and Thomas Stützle

Table of Contents
  1. Abstract
  2. Instances
  3. Empirical Scaling Analyser output
  4. Figures
  5. Papers

1. Abstract:

We study the empirical scaling of the running time required by state-of-the-art exact and inexact TSP algorithms for finding optimal solutions to Euclidean TSP instances as a function of instance size. In particular, we use a recently introduced statistical approach to obtain scaling models from observed performance data and to assess the accuracy of these models. For Concorde, the long-standing state-of-the-art exact TSP solver, we compare the scaling of the running time until an optimal solution is first encountered (the \emph{finding time}) and that of the overall running time, which adds to the finding time the additional time needed to complete the proof of optimality. For two state-of-the-art inexact TSP solvers, LKH and EAX, we compare the scaling of their running time for finding an optimal solution to a given instance; we also compare the resulting models to that for the scaling of Concorde's finding time, presenting evidence that both inexact TSP solvers show significantly better scaling behaviour than Concorde.

Keywords: empirical scaling analysis, running time, empirical performance models, traveling salesman problem, optimal solutions

2. Benchmark Instances:

For our analysis, we used a benchmark sets of Randum Uniform Euclidean (RUE) instances, which we also had used in earlier research efforts. These instances were generated using the portgen generator from the 8th DIMACS implementation challenge for the TSP, by placing n points in a 100000 times 100000 square uniformly at random and computing Euclidean distances between these points. There are 1000 instances for each instance size n from 500 to 2000 and 100 instances for each size in 2500, 3000, 3500, 4000, and 4500. RUE instances are among the most widely studied classes of Euclidean TSP instances. Most of these instances with only few exceptions for instances sizes 4000 and 4500 have been solved to optimality by the concorde solver using Qsopt as the linear programming solver. Optimal solution values (or the best-known solutions found by either the LKH or EAX heuristics in case we do not know proven optimal solutions) are available here.
Instance size #Instances
500 1000
600 1000
700 1000
800 1000
900 1000
1000 1000
1100 1000
1200 1000
1300 1000
1400 1000
1500 1000
1600 1000
1700 1000
1800 1000
1900 1000
2000 1000
2500-4500 100 each size

3. Empirical Scaling Analyser outputs:

Below are linked the outputs generated by the empirical scaling analyser software package, which was developed by Mu and Hoos. The tool takes a file of solver runtimes (sample) as input, automatically fits and evaluates parametric models, and generates a PDF report for the analysis results (sample). The models are fitted using standard numerical methods, and are challenged by extrapolation using a bootstrap approach. For detailed information about the methodology, please refer to the papers below. For a try of the tool with your own data, please see the Empirical Scaling Analyser (ESA) webpage.

Below are given the reports output by the tool that give the scaling analysis for the run-time data obtained by (i) Concorde, find and prove, (ii) Concorde, find only, (iii) LKH 2, and (iv) EAX. The additional analyses have been done for the 75 and the 90 percent quantile of the search cost distributions.

Algorithm Q75 Q90
Concorde, find and prove Q75 predictions Q90 predictions
Concorde, find Q75 predictions Q90 predictions
LKH 2 Q75 predictions Q90 predictions
EAX Q75 predictions Q90 predictions

4. Figures

For a more detailed inspection of the plots used in Figures 3, 5, 6, 7, and 8 in the article, they are made available here.
Here are also available the solution cost distributions (SCDs) for Concorde find+prove and EAX. In each plot are given the SCDs for instance sizes 1000, 2000, and 3000.

5. Papers