A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem

Olaf Mersmann, Bernd Bischl, Heike Trautmann, Markus Wagner, Jakob Bossek, Frank Neumann

Research output: Contribution to journalArticleResearchpeer-review

67 Citations (Scopus)

Abstract

Meta-heuristics are frequently used to tackle NP-hard combinatorial optimization problems. With this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the traveling salesperson problem (TSP). Although 2-opt is widely used in practice, it is hard to understand its success from a theoretical perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt.

Original languageEnglish
Pages (from-to)151-182
Number of pages32
JournalAnnals of Mathematics and Artificial Intelligence
Volume69
Issue number2
DOIs
Publication statusPublished - 2013
Externally publishedYes

Keywords

  • 2-opt
  • Classification
  • Feature selection
  • MARS
  • TSP

Cite this