On the empirical scaling of running time for finding optimal solutions to the TSP

Zongxu Mu (), Jérémie Dubois-Lacoste (), Holger H. Hoos () and Thomas Stützle ()
Additional contact information
Zongxu Mu: University of British Columbia
Jérémie Dubois-Lacoste: Université libre de Bruxelles (ULB)
Holger H. Hoos: University of British Columbia
Thomas Stützle: Université libre de Bruxelles (ULB)

Journal of Heuristics, 2018, vol. 24, issue 6, No 3, 879-898

Abstract: 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 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: Traveling salesman problem; Lin-Kernighan algorithm; Evolutionary algorithms; Scaling analysis; Concorde; Empirical analysis (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-018-9374-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:24:y:2018:i:6:d:10.1007_s10732-018-9374-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-018-9374-0

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().