Instance space analysis for the metric TSP
joint work with M. Mastrolilli
We are studying the practical performance of exact and heuristic algorithms for the Symmetric Traveling Salesman Problem (TSP) using Instance Space Analysis. The project focuses on comparing Concorde and LKH-3 across a diverse set of TSP instances, from easy to challenging cases. By analyzing solution quality over time and the time required to reach different optimality gaps, we aim to identify regions of the instance space where one algorithm performs better than the other. The final goal is to provide practical guidance on when to use an exact solver or a heuristic approach.