Our computation was carried out on a cluster of Intel Xeon dual-processor machines.  This cluster was also used for other purposes during our computing period, making it difficult to provide a meaningful estimate of the "wall-clock" running time for the computation.  Instead, we measure CPU time in terms of a single processor Intel Xeon running at 2.8 GHz.  In other words, we measure how much time it would take if we carried out the same computation on a single processor machine rather than the large parallel cluster.

In our first table we report the running time for the cutting-plane procedure on our initial LP. Each line in the table corresponds to a pass of the cutting-plane process with local cuts of the indicated size.  The CPU times are the total (cumulative) time used in all of the cutting-plane passes up to that point.

Local Cut Size Cumulative CPU Seconds
1614,116
2025,502
2441,889
2875,370
32115,550
36142,506
40215,243
44219,503
48242,897

For this first LP, we plot below the % optimality gap versus the CPU time used.  Note that the optimality gap is plotted on a log scale.

Plot of LP Time

The total times for each of the five cutting-plane runs to create the root LPs is given in the following table.

LP Run CPU Seconds
1242,897
2154,566
3143,287
4186,689
5290,425

The five branch-and-cut runs made up the bulk of the computation.  The CPU time roughly doubled for each run as we increased the size of the tree and also allowed more time for the cutting-plane routines and for the routines that selected the problem subdivisions (the "branching" strategy).  A summary of the CPU times for the runs is given in the following table.

B&C Run Nodes CPU Seconds
12,01134,585,460
22,965138,864,297
310,355372,876,611
414,367717,615,549
5167,2631,408,909,118

The total CPU time for the five cutting-plane runs and for the five branch-and-cut runs was approximately 84.8 CPU years.

The last piece of the computation was a final checking of the validity of the 14,827,429 (non-subtour) cutting planes that were used in the Sweden computation.  The checking process was started on January 28, 2004 and completed on May 20, 2004.  The total CPU time was 222,796,246 CPU seconds, adding approximately 7.1 CPU years to the computation.

This last part of the computation was redundant in that each of the cuts was already verified when it first appeared in our branch-and-cut runs, and we have not included the 7.1 years in our estimate of the total CPU time used to solve the Sweden TSP.  With this additional time, the estimate would grow to 91.9 CPU years on a single Intel Xeon 2.8 GHz processor.