Leveraging TSP Solver Complementarity through Machine Learning

Area of Science:

• Computer Science
• Operations Research
• Algorithm Analysis

Background:

• The Traveling Salesperson Problem (TSP) is a well-known NP-hard problem with extensive research into solution methods.
• Numerous inexact solvers have been developed for the TSP, but direct comparisons are limited.

Purpose of the Study:

• To directly compare the performance of five leading inexact TSP solvers: LKH, EAX, and their restart variants, plus MAOS.
• To develop and evaluate an algorithm selector that leverages solver complementarity for improved TSP solutions.

Main Methods:

• Direct performance comparison of LKH, EAX, restart variants, and MAOS on benchmark TSP instances.
• Development of an algorithm selector based on per-instance solver effectiveness.
• Analysis of factors contributing to the selector's performance improvement.

Main Results:

• Demonstrated complementary performance among the compared TSP solvers, indicating no single algorithm is universally superior.
• The developed algorithm selector significantly outperformed the best single solver across benchmark instances.
• Identified key drivers behind the enhanced performance achieved by the algorithm selector.

Conclusions:

• Algorithm selection based on per-instance performance is a highly effective strategy for solving the Euclidean TSP.
• The findings represent a significant advancement in the state-of-the-art for solving the Euclidean TSP.
• Complementarity among solvers is a crucial factor for optimizing TSP solution strategies.