Lunch & Learn: In pursuit of the salesman: Mathematics at the limits of computation with Bill Cook

TSPxkcd120.jpgThe traveling salesman problem, or TSP for short, is easy to state: given a number of cities along with the cost of travel between each pair of them, find the cheapest way to visit them all and return to your starting point. Simple to state, but remarkably difficult to solve! Despite decades of research by top applied mathematicians around the world, in general it is not known how to significantly improve upon simple brute-force checking. It is a real possibility that there may never exist an efficient method that is guaranteed to solve every instance of the problem. This is a deep mathematical question:

Is there an efficient solution method or not? The topic goes to the core of complexity theory concerning the limits of feasible computation. For the stout-hearted who would like to tackle the general version of the TSP, the Clay Mathematics Institute will hand over a $1,000,000 prize to anyone who can either produce an efficient general method or prove an impossibility result.

The complexity question that is the subject of the Clay Prize is the Holy Grail of traveling-salesman-problem research and we may be far from seeing its resolution. This is not to say that mathematicians have thus far come away empty-handed. Within the theoretical community the problem has led to a large number of results and conjectures that are both beautiful and deep. In the arena of exact computation, an 85,900-city challenge problem was solved in 2006, when the optimal tour was pulled out of a mind-boggling number of candidates in a computation that took the equivalent of 136 years on top-of-the-line computer workstations.

BillCook.jpgAt the December 16 Lunch ‘n Learn, Bill Cook, who holds the Chandler Family Chair in the School of Industrial and Systems Engineering at Georgia Tech, reviewed the rich history, the varied applications, and some of the computation techniques involved in this fascinating problem. He began with a remarkable image from 1962, a contest run by Proctor and Gamble with a $10,000 first prize that challenged participants to help officers Toody and Muldoon to find the shortest round trip involving 33 separate locations. At that time, emphasized Cook, no one knew how to solve such problems, and yet it is clear that there is a specific optimal answer for the 1962 contest.
By clear contrast, it is not clear that anyone will ever be able to claim successfully an efficient solution to every TSP problem for the $1,000,000 prize. Generally, mathematicians seems to betting against such a solution. Cook provided quotes from three decades. In 1956, Merrill Flood was the first to suggest that there might not be a solution: “In fact, there may well be no general method for treating the problem and impossibility results would also be valuable.” In 1965, Jack Edmonds conjectured “that there is no good algorithm for the traveling salesman problem.” And in 1972, Richard Karp, “In this paper we give theorems which strongly suggest, but do not imply, that these problems, as well as many others, will remain intractable perpetually.” Solve the TSP, suggested Karp, and you will have found a solution to other intractable problems, the so called NP-hard problems.

In many respects, suggested Cook, determining whether or not there exists an efficient solution method for the TSP and the other NP-hard problems is one of the most important questions in mathematics. Note the vast investment in Internet infrastructure, which is itself constructed on the assumption that we cannot solve certain problems that would become easy if we could solve the TSP. Purchases over the Internet are secure because we believe that certain computations are too difficult to decrypt. But a solution to the TSP would also have great positive effects, such as lessening delays at the airport and providing powerful tools to economists to sustain efficient economic activity,
While we may not be able to solve the TSP completely, says Cook, we are now able to solve efficiently many of the practical examples. As it turns out, there really are traveling salesman, circuit court judges, and circuit-riding preachers who would benefit from such efficiency.

On the practical side, solution methods are used to compute optimal or near-optimal tours for a host of applied modern problems on a daily basis. Modern TSP analysis plotted postal routes in Denmark, the delivery of meals-on-wheels, an optimal path for a pilot determined to visit every town North Carolina in a single day, guiding drills that are cutting a series of holes, and plotting telescopes’ targeting of astronomic features. Recent work at the National Institute for Health by Agarwala and Schaeffer worked to integrate the TSP code into a framework for even the reading of base-pairs in genome sequencing.
With the exponential advance in processing power, TSP solutions have advanced steadily, from 49 cities in 1954, to 318 cities in 1980, 3,038 cities in 1992, and in 2006, an 85,900 city solution. Techniques used to solve the TSP problems have migrated to other domains such as DNA computing, neural nets, and even ant-colony optimization.

In 1973, Princeton’s own Brian Kernighan, who with S. Lin at Bell Labs proposed an approach to the TSP that remains at the core of most TSP applications, a hill-climbing technique that follows the terrain to move higher and higher towards individual peaks.
Cook concluded with a review of other methods, but the larger question remains. Is there a single, efficient method to solve the TSP. We may never know, suggests Cook, but useful applications continue to emanate from a surprising variety of disciplines.

Bill Cook received his Ph.D. in Combinatorics and Optimization from the University of Waterloo in 1983. Cook spent two years as an Alexander von Humboldt Research Fellow at the University of Bonn, and he has held positions at Cornell, Columbia, Bellcore, Rice, and Princeton. He is a former Editor-in-Chief of Mathematical Programming (1999–2007) and he is currently the Editor-in-Chief and Founding Editor of the new journal Mathematical Programming Computation. Cook is also a member of the Editorial Boards of Mathematics of Operations Research, SIAM Journal on Discrete Mathematics, and
SIAM Journal on Optimization.

Together with David Applegate, Robert Bixby, and Vasek Chvatal, he was awarded the 2000 Beale-Orchard-Hayes Prize by the Mathematical Programming Society and in 2007 their book The Traveling Salesman Problem: A Computational Study
(Princeton University Press) was awarded the Lanchester Prize by INFORMS; at an earlier stage, their TSP work was named one of the Top 50 Science Stories of 1992 by Discover Magazine. Cook was named the 2003 I. E. Block Community Lecturer by the Society for Industrial and Applied Mathematics (SIAM) and he was named a SIAM Fellow in 2009.

The podcast is available.