The tour of South Korean bars is the largest road-map instance of the TSP that has been solved to date. It was by no means an easy task, but we benefitted from experience obtained in solving four other large examples of the TSP.
| Point Set | Year Solved | B&B Size | B&B CPU Time | Total CPU Time | Elapsed Time |
|---|---|---|---|---|---|
| 49,603 US historic sites | 2016 | 830,505 | 178.7 years | 231 years | 10 months | 49,687 UK pubs | 2018 | 557,271 | 200.6 years | 250 years | 18 months |
| 57,912 Dutch monuments | 2021 | 386,025 | 90.0 years | 97 years | 6 months |
| 40,426 Japanese stores | 2024 | 113,651 | 23.4 years | 43 years | 2 months |
In the table columns, "B&B Size" reports the number of subproblems in the branch-and-bound search tree, "B&B CPU Time" reports the computer time for the search (if run on a single processor core of our Linux server), "Total CPU Time" reports a very rough estimate of the total time for solving the example (including building the linear-programming relaxation), and "Elapsed Time" reports the calendar months for the computation (from start to finish).
The CPU times, measured in years, make clear the challenge of solving TSP instances of this size. Our main computations for these examples were carried out on a network of Linux servers at the University of Waterloo, permitting the use of up to several hundred processor cores when the servers were not otherwise busy with day-to-day projects. The reported times are the sum of the times over the processor cores utilized in the long computations.
A striking feature of the table is the frighteningly large number of subproblems in the branch-and-bound search trees. To have a chance at solving korea81998, we knew our optimization strategy had to be adjusted in an attempt to decrease the size of search.
Using 44 processor cores on a Linux sever equipped with two 2.10GHz Intel Xeon Gold 6238 CPUs (each with 22 cores), the OSRM software calculated the korea81998 distance table in a little over 1.5 days. After a quick check of the data, I sent the TSPLIB file to Keld Helsgaun on December 10, 2024. Keld is the world's leading expert at finding high-quality TSP tours. He is the creator of the LKH code, long the standard in TSP heuristic-search software.
An hour after Keld received the korea81998 file, he sent a quick note stating that he had found an LKH tour of length 15399990. The following day Keld improved his result, finding a tour of length 15386177 by merging 47 LKH tours. By December 14, Keld had found tours of the same length 15386177 in three independent runs of LKH+MERGE.
This is similar to the experience we had with the 40,426-stop Japanese TSP solved in November 2024. In that case, Keld's result was later proved to be a shortest-possible tour. So we were confident that 15386177 must be very close to the optimal value. In another two months we knew for sure, the LKH+MERGE tours are optimal for korea81998.
In the computation that produced the optimality proof, we followed standard practice and initiated our branch-and-bound search with an upper bound of 1 greater than the best-known tour length, to force the search to reproduce an optimal solution (as a check on the run). But having the strong bound at the start was a great help in the computation.
The initial bound guides the Concorde code in a number of ways. It allows for subproblems to be pruned in the branch-and-bound search, it lets the code eliminate edges that cannot be in any tour better than the initial bound, and it sets the tolerances for switching between faster and slower routines for finding cutting planes.
But for the largest instances we study, the greatest help the LKH tour provides is on the human-decision side. For more modest-sized instances, such as the 2,141-stop Daejeon tour, we can just hit the Concorde start button with default settings and wait for the optimal solution. This is not case for the largest instances, where we are pushing the limits of solvability to study potential improvements in the solution process. Here we are making adjustments on-the-fly, switching between the cutting-plane method and branch-and-bound search, experimenting with new cutting-plane routines, testing branching rules, and more. These choices depend heavily on the gap between the lower bound we are computing and the upper bound given by the best-known tour.
The key to proving a tour is shortest possible is to construct a linear-programming (LP) relaxation for the TSP instance, that is, an LP model such that every TSP tour is a candidate solution. If the optimal LP value (or, more generally, the value of any dual LP solution) is β, then no tour can have length less than β. That is, β is a lower bound for the TSP, giving us a means to establish a quality guarantee on the length of our tour.
An LP model for the TSP assigns to every point-to-point connection a (possibly fractional) value between 0 and 1. A point-to-point connection joins a pair of stops; it is called a link or an edge. A tour can be represented as an LP solution where every link is assigned either 0 or 1; the links assigned the value 1 correspond to those that are used in the tour. The LP constraints are rules that are satisfied by all tour solutions. A basic rule, called a degree equation, is that for every stop the values of the links meeting the stop must sum to two. An important further rule, called a subtour inequality, is that for any subset of stops S, the values of the links having one end in S and the other end not in S must be at least two.
An LP solution that has all values 0 or 1 and satisfies all degree equations and subtour inequalities is a tour. Great, but an LP solution might have fractional values. This is where the difficult work of the cutting-plane method starts. The process adds more and more rules, increasing the lower bound β and forcing the LP solution to be closer to all 0-1 values.
In January and into February, we slowly built our LP relaxation, using Concorde's implementation of the cutting-plane method to repeatedly improve the LP's quality, that is, to increase the lower bound it produced. In comparison with our previous four road-map instances, we used longer computations to find cutting planes. The changes in strategy include the following.
A branch-and-bound search attempts to increase the value of the lower bound by repeatedly splitting the set of candidate tours into two smaller sets. For example, we might chose a link between two stops and split the remaining tours into those that definitely use the link and those that definitely do not use the link. We thus create two new child subproblems from a single parent. Applying the cutting-plane method to each child, we can possibly improve in each case the LP bound given by the parent, and thus increase our overall lower bound. And we can continue the process by branching in each of the subproblems.
In the korea81998 computation, we adopted the slow (but careful) technique called "tentative branching" to identify the structure used to split a problem into two child subproblems. Each time we needed to make a branch, we evaluated 16 choices for the structure, carrying out cutting-plane processes on each pair of candidate child subproblems, before making the final choice for the branching step. This process is costly in terms of computation time per branch, but it tends to produce smaller branch-and-bound search trees, a main target in our study.
Together with tentative branching, we also adopted the repeated use of the tighten technique on each subproblem. Compared with our previous computations, this choice required much more time per search node, but the improved LP bounds could again help to reduce the size of the search tree.
The computation is summarized in the following table.
| Point Set | Year Solved | B&B Size | B&B CPU Time | Total CPU Time | Elapsed Time |
|---|---|---|---|---|---|
| 81,998 Korean bars | 2025 | 2,121 | 10.2 years | 44 years | 3 months |
We were of course very happy to see the small search tree and to solve such a large TSP instance. But it raises the natural question of whether the methods we employed were just lucky on this particular example. This is a difficulty with large-scale, time-consuming computational work, where we do not have the resources to make a sufficient number of trials to evaluate alternative techniques. On the other hand, it gives us an added reason to look at even larger examples. Excelsior!
The tour map-drawings were created with the Leaflet open-source JavaScript library for mobile-friendly interactive maps and make use of map tiles built by OpenStreetMap, by Carto Basemaps and by Stadia Maps.