by Zongxu Mu, Jérémie Dubois-Lacoste, Holger H. Hoos, and Thomas Stützle
2017
| Table of Contents |
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
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 |
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 |
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.