Bill Cook, Professor at Georgia Tech, has an article in the “Campaign Stops” blog of the New York Times outlining the plight of the candidates vying for the Republican nomination for the U.S. presidency currently campaigning in Iowa. It is a quirk of American politics that a small state can take on outsized importance in the U.S. political process, but historically states such as Iowa and New Hampshire vote early on “their” nominees, while larger states such as California and New York come later. The effect of this is that candidates spend a tremendous amount of time in relatively low-population states. This is not necessarily a bad thing: the rest of the country gets to watch the candidates do practically one-on-one politics and we get to see how they handle the varied interests in these states in great detail.
At least two of the candidates in Iowa (Rick Santorum and Michelle Bachmann) will have visited all 99 counties in that state, leading up to the January 3, 2012 caucus date (it is a further quirk of American politics that some state don’t hold elections as such: a caucus is a gathering of neighbors to discuss, debate, and choose their delegates to a state convention which then will choose among the candidates).
The question Bill asked was “What is the quickest way to visit all 99 counties?”. Actually, Bill asked the question “What is the quickest way to visit the county seats of all 99 counties?”, a somewhat easier problem. This is an instance of the Traveling Salesman Problem, and problem Bill has studied for years. Bill is the primary author of Concorde, clearly the best code for finding optimal Traveling Salesman tours. As Bill explains in the New York Times article, the TSP is formally a hard problem, but particular instances can be solved to optimality:
Leaving Des Moines, we have 98 choices for our second stop, then, for each of these, 97 choices for the third stop, then 96 choices for the fourth stop, and so on until we hit our last county and drive back to Des Moines. Multiplying all of these choices gives the number of possible routes through Iowa. And it is a big number, roughly 9 followed by 153 zeros. No computer in the world could look through such an enormous collection of tours one by one.
The task of choosing the best of the tours is known as the traveling salesman problem, or T.S.P. I work in an applied mathematics field called operations research, which deals with the optimal use of scarce resources, and the T.S.P. is a specialty of mine.
…
This is a tough challenge, but to tour Iowa we do not need a general solution for the problem, we just have to handle our particular 99-city example. We were able to do this using a technique known as the cutting-plane method.
The Iowa instance is, pre
sumably, not much of a challenge for Concorde: that code has found solutions to TSP instances with tens of thousands of cities. I am sure that most of the work, which Bill did together with Alain Kornhauser and Robert Vanderbei of Princeton, was in determining the distances between the 99 county seats. The actually route optimization would be a matter of seconds or less. The result is a 55.5 hour tour, traveling at legal speed limits.
If you would like to experiment with TSPs of your own, the excellent NEOS solvers allow you to upload your own instances and run Concorde on them.
Stay tuned for more from Bill Cook as we count down to the publication of his book In Pursuit of the Traveling Salesman, to be published in January. Trust me, you are going to like the book, so show some support for Bill by liking the Facebook page!