Certification of an optimal TSP tour through 85,900 cities
Session date: 11 September 2023
Session host: Konstantin Sidorov
Summary:
In this session I will go over the integer-programming flow for solving traveling salesman problem instances (utilized, among others, by Concorde TSP solver) and introduce the approach by Applegate et al. for logging the solver steps that lead to the optimal tour. This approach is used to justify an optimal tour on pla85900, the largest instance from the TSPLIB collection.