Solving a large instance of the TSP is not an easy task. The full computation for nl57912 used a total of 96.9 years of computer time (if run on a single processor core of one of our Linux servers). The computation was carried out between September 2020 and March 2021 at the University of Waterloo on a network of 10 servers, each with 32 cores. The TSP computation ran when the servers were not otherwise busy with day-to-day projects.
The total time was actually less than we used on the two previous map-distance instances: the 49,603-point US problem took 179 years (spread over 10 months) and the 49,687-point UK problem took 250 years (spread over 18 months).
For a difficult NP-hard problem like the TSP, the three running times are remarkably similar. But there may be two reasons behind the quicker NL computation. First, with the full table of travel distances we were able to be more aggressive in selecting edges (pairs of points) to include in our linear-programming relaxations, versus the careful approach we adopted when forced to query Google Maps for the length of each edge individually. Second, although it is nearly impossible to say this beforehand, the distribution of points in nl57912 may make it somewhat easier than the US and UK examples. You can see the special structure in some of the images, where monument markers are nicely lined up along certain streets (that have neighboring houses or buildings with interesting histories).
The nl57912 instance was created in the summer of 2020, and we began working with the data set on September 3, 2020. A first tour of length 20,253,564 meters (so 502 meters longer than an optimal tour) was found by the LKH code on September 6. That is a very good result, but a new parallel version of LKH did even better, improving the tour length by 186 meters on September 27. (Note that all distances in the table are integer values, so the tour length will be an integer.)
We found no further improvements over the following weeks, so we initiated our branch-and-bound search on November 16 with an upper bound of 20,253,379. It is a standard practice to give the branch-and-bound solver an upper bound of 1 greater than the best known tour, to force the search to reproduce an optimal solution (as a check on the computation).
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 initial tour.
During September and October, 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).
By November 16, we had an LP relaxation of value 20,251,280, showing our tour was at most 2,098 meters longer than an optimal tour. We used this LP as the starting point for our branch-and-bound search.
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 an edge between two monuments and split the remaining tours into those that definitely use the edge and those that definitely do not use the edge. 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.
In the first step of our branch-and-bound search, we created child subproblems that gave LP bounds of value 20,251,395 and 20,251,426. Thus we knew there could be no tour shorter than the smaller of these two values, so we had a new lower bound of 20,251,395. In a single step, we improved the gap to our tour from 2,098 meters down to 1,983 meters. A long way to go, but it was a start.
By February 26, 2021, we had created a branch-and-bound search tree with 34,649 subproblems that reduced the gap to 359 meters. This run had already itself used 68.0 compute years, and, due to the large number of subproblems that needed to be processed, I had planned to shut it down. The idea was to improve the starting LP relaxation by using new linear inequalities created during the run, then try our luck at another branch-and-bound search.
But when setting up the shut-down process, I saw that the search had produced that night a new tour of length 20,253,247, improving our initial tour by 131 meters. The was unexpected, since in both the US and UK examples the LKH tour later proved to be optimal. I immediately sent the result to Keld Helsgaun, and four hours later he replied that LKH merged our two tours to obtain a further improvement of 185 meters, resulting in a tour of length 20,253,062.
This new tour reduced the gap to 43 meters, and the branch-and-bound search (after a total of 386,025 subproblems) was able to prove that it was in fact an optimal tour.
The images below are snapshots of the branch-and-bound search used to solve nl57912, each depicting the search tree on the indicated date. The active nodes of the trees (those representing subproblems that have not yet been processed) are colored either red or magenta. The red nodes are those that have not yet gone through additional rounds of the cutting-plane procedure after the branching step (the subproblems retain the cutting planes that were found for their parent, but no additional cuts have yet been generated). The height of a node indicates the optimal value of its LP relaxation.
At the top of each image, we display the date, together with the lower bound the search has established and the number of active subproblems. Notice the red/magenta line of active nodes slowly moving down the images, as the search progresses to better and better lower bounds.
Click on the images to see high-resolution versions.
