Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated
  Algorithm Selection
  The Traveling-Salesperson-Problem (TSP) is arguably one of the best-known
NP-hard combinatorial optimization problems. The two sophisticated heuristic
solvers LKH and EAX and respective (restart) variants manage to calculate
close-to optimal or even optimal solutions, also for large instances with
several thousand nodes in reasonable time. In this work we extend existing
benchmarking studies by addressing anytime behaviour of inexact TSP solvers
based on empirical runtime distributions leading to an increased understanding
of solver behaviour and the respective relation to problem hardness. It turns
out that performance ranking of solvers is highly dependent on the focused
approximation quality. Insights on intersection points of performances offer
huge potential for the construction of hybridized solvers depending on instance
features. Moreover, instance features tailored to anytime performance and
corresponding performance indicators will highly improve automated algorithm
selection models by including comprehensive information on solver quality.
