Solving an instance of the traveling salesman problem (TSP) does not mean finding a good tour or even finding one that is better than any previously known.  To solve a TSP we need to find an absolute shortest tour and to know indeed that no better tour is possible. 

Given the complexity of the calculations it seems unlikely that we will ever be able to construct a proof that our Sweden tour is optimal that can be checked completely by hand, without the aid of a computer.  Indeed, our Sweden TSP computation used 84.8 CPU years to verify that a best-possible tour had been found.

Our verification process included numerous checks to ensure that the computation was accurate and we describe the techniques used in the following pages.

• Geometric lower bounds with control zones
• Subtour elimination
• The cutting-plane method
• Local cuts
• Branch-and-cut
• Accuracy of computations