Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection
L. Kotthoff, P. Kerschke, H. Hoos, H. Trautmann, in: C. Dhaenens, L. Jourdan, M.-E. Marmion (Eds.), Learning and Intelligent Optimization, Springer International Publishing, Cham, 2015, pp. 202–217.
Download
No fulltext has been uploaded.
Conference Paper
| English
Author
Kotthoff, Lars;
Kerschke, Pascal;
Hoos, Holger;
Trautmann, HeikeLibreCat 
Editor
Dhaenens, Clarisse;
Jourdan, Laetitia;
Marmion, Marie-Eléonore
Abstract
We investigate per-instance algorithm selection techniques for solving the Travelling Salesman Problem (TSP), based on the two state-of-the-art inexact TSP solvers, LKH and EAX. Our comprehensive experiments demonstrate that the solvers exhibit complementary performance across a diverse set of instances, and the potential for improving the state of the art by selecting between them is significant. Using TSP features from the literature as well as a set of novel features, we show that we can capitalise on this potential by building an efficient selector that achieves significant performance improvements in practice. Our selectors represent a significant improvement in the state-of-the-art in inexact TSP solving, and hence in the ability to find optimal solutions (without proof of optimality) for challenging TSP instances in practice.
Publishing Year
Proceedings Title
Learning and Intelligent Optimization
Page
202–217
ISBN
LibreCat-ID
Cite this
Kotthoff L, Kerschke P, Hoos H, Trautmann H. Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection. In: Dhaenens C, Jourdan L, Marmion M-E, eds. Learning and Intelligent Optimization. Springer International Publishing; 2015:202–217.
Kotthoff, L., Kerschke, P., Hoos, H., & Trautmann, H. (2015). Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection. In C. Dhaenens, L. Jourdan, & M.-E. Marmion (Eds.), Learning and Intelligent Optimization (pp. 202–217). Springer International Publishing.
@inproceedings{Kotthoff_Kerschke_Hoos_Trautmann_2015, place={Cham}, title={Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection}, booktitle={Learning and Intelligent Optimization}, publisher={Springer International Publishing}, author={Kotthoff, Lars and Kerschke, Pascal and Hoos, Holger and Trautmann, Heike}, editor={Dhaenens, Clarisse and Jourdan, Laetitia and Marmion, Marie-Eléonore}, year={2015}, pages={202–217} }
Kotthoff, Lars, Pascal Kerschke, Holger Hoos, and Heike Trautmann. “Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection.” In Learning and Intelligent Optimization, edited by Clarisse Dhaenens, Laetitia Jourdan, and Marie-Eléonore Marmion, 202–217. Cham: Springer International Publishing, 2015.
L. Kotthoff, P. Kerschke, H. Hoos, and H. Trautmann, “Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection,” in Learning and Intelligent Optimization, 2015, pp. 202–217.
Kotthoff, Lars, et al. “Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection.” Learning and Intelligent Optimization, edited by Clarisse Dhaenens et al., Springer International Publishing, 2015, pp. 202–217.
Google Scholar
ISBN Search