Leveraging TSP Solver Complementarity through Machine Learning

P. Kerschke, L. Kotthoff, J. Bossek, H.H. Hoos, H. Trautmann, Evolutionary Computation (ECJ) 26 (2018) 597–620.

Download
No fulltext has been uploaded.
Journal Article | English
Author
Kerschke, Pascal; Kotthoff, Lars; Bossek, JakobLibreCat ; Hoos, Holger H.; Trautmann, HeikeLibreCat
Abstract
The Travelling Salesperson Problem (TSP) is one of the best-studied NP-hard problems. Over the years, many different solution approaches and solvers have been developed. For the first time, we directly compare five state-of-the-art inexact solvers—namely, LKH, EAX, restart variants of those, and MAOS—on a large set of well-known benchmark instances and demonstrate complementary performance, in that different instances may be solved most effectively by different algorithms. We leverage this complementarity to build an algorithm selector, which selects the best TSP solver on a per-instance basis and thus achieves significantly improved performance compared to the single best solver, representing an advance in the state of the art in solving the Euclidean TSP. Our in-depth analysis of the selectors provides insight into what drives this performance improvement.
Publishing Year
Journal Title
Evolutionary Computation (ECJ)
Volume
26
Issue
4
Page
597–620
LibreCat-ID

Cite this

Kerschke P, Kotthoff L, Bossek J, Hoos HH, Trautmann H. Leveraging TSP Solver Complementarity through Machine Learning. Evolutionary Computation (ECJ). 2018;26(4):597–620. doi:10.1162/evco_a_00215
Kerschke, P., Kotthoff, L., Bossek, J., Hoos, H. H., & Trautmann, H. (2018). Leveraging TSP Solver Complementarity through Machine Learning. Evolutionary Computation (ECJ), 26(4), 597–620. https://doi.org/10.1162/evco_a_00215
@article{Kerschke_Kotthoff_Bossek_Hoos_Trautmann_2018, title={Leveraging TSP Solver Complementarity through Machine Learning}, volume={26}, DOI={10.1162/evco_a_00215}, number={4}, journal={Evolutionary Computation (ECJ)}, author={Kerschke, Pascal and Kotthoff, Lars and Bossek, Jakob and Hoos, Holger H. and Trautmann, Heike}, year={2018}, pages={597–620} }
Kerschke, Pascal, Lars Kotthoff, Jakob Bossek, Holger H. Hoos, and Heike Trautmann. “Leveraging TSP Solver Complementarity through Machine Learning.” Evolutionary Computation (ECJ) 26, no. 4 (2018): 597–620. https://doi.org/10.1162/evco_a_00215.
P. Kerschke, L. Kotthoff, J. Bossek, H. H. Hoos, and H. Trautmann, “Leveraging TSP Solver Complementarity through Machine Learning,” Evolutionary Computation (ECJ), vol. 26, no. 4, pp. 597–620, 2018, doi: 10.1162/evco_a_00215.
Kerschke, Pascal, et al. “Leveraging TSP Solver Complementarity through Machine Learning.” Evolutionary Computation (ECJ), vol. 26, no. 4, 2018, pp. 597–620, doi:10.1162/evco_a_00215.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar