A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem

Mersmann O, Bischl B, Trautmann H, Wagner M, Bossek J, Neumann F


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.

Keywords
TSP; 2-opt; Classification; Feature selection; MARS



Publication type
Article in Journal

Peer reviewed
Yes

Publication status
Published

Year
2013

Journal
Annals of Mathematics and Artificial Intelligence

Volume
69

Start page
151

End page
182

Language
English