Given a collection of points, the TSP asks for the shortest route to visit them all. Simple enough. But even a whisper of the problem strikes fear in the heart of the computing world. Last year, a Washington Post article reported it would take “1,000 years to compute the most efficient route between 22 cities.” This claim, however, ignores 70 years of intense study in the OR community. A 22-city TSP can be handled in a snap with modern algorithms, even on an iPhone. Going larger, we describe techniques that have been used to solve to precise optimality examples with nearly 50,000 points and Google Map walking distances. And if you need to visit the nearest 2,079,471 stars, there is a route, ready to go, that is guaranteed to be no more than 1.00002 times longer than a shortest possible tour.
This work follows a long line of computational research going back to Julia Robinson in 1949 and Dantzig, Fulkerson, and Johnson in 1954. The general setting is the following. Complexity theory suggests there are limits to the power of general-purpose computational techniques, in engineering, science and elsewhere. But what are these limits and how widely do they constrain our quest for knowledge? The TSP can play a crucial role in this context, demonstrating whether or not focused efforts on a single, possibly unsolvable, model will produce results beyond our expectations.
We will discuss the history of the TSP and its applications, together with recent computational efforts towards exact and approximate solution methods. The talk is based on joint work the David Applegate, Daniel Espinoza, Marcos Goycoolea, and Keld Helsgaun.