The Problem of the Traveling Politician

December 21, 2011, 9:00 pm
The Problem of the Traveling Politician
By WILLIAM COOK

Politicians have always been heavy travelers, but recent news out of Iowa takes the notion of hitting the campaign trail to new extremes. Rick Santorum has toured all 99 counties and he is back criscrossing the state. Thursday is day seven of Michele Bachmann’s own 99-county tour. She plans to cover the state in 10 days, with time off for Christmas. Rick Perry and Newt Gingrich each announced 44-city bus tours leading up to the January caucuses. Not to be left out, Mitt Romney announced on Tuesday that he would begin his three-day tour on Dec. 28.

With all this movement, we thought we might lend a hand and offer a suggestion for saving time and gasoline.

If you want to join in and cover all 99 counties, then you should follow the route shown on the map above, which I created together with Alain Kornhauser and Robert Vanderbei, professors of operations research and financial engineering at Princeton.

The white path traces the quickest possible tour through the state, hitting all 99 county seats in 55.5 hours and 2,739 miles. The trip is circular, so you can start and stop at any of the 99 and travel the same total distance.

To give you a feeling for the political landscape faced by the traveling candidates, in the image the color scheme for the Iowa counties is adopted from Vanderbei’s Purple America. Blue is for Democratic candidates, red is for the Republicans, and green is for all the others.

Each county’s color is a mix of these three components in proportion to the results for that county in the 2008 presidential election. Sioux County in the west is solidly red and Johnson County in the east is very blue, but otherwise this year’s candidates must travel through various shades of purple as they move across the state. In no county did third-party candidates gather more than a very small percentage of the votes, so the green coloring affects the overall purpleness but isn’t really visible.

In constructing the optimal tour, the first step was to compute the point-to-point trips, from county seat to county seat. We needed to do this for each pair of counties, so that’s nearly 10,000 individual trips. To do this, we used the CoPilot software developed by Kornhauser.

For each of the pairs, the software computed the driving time for the quickest route between the two county seats; we also obtained the shortest mileage for each pair, but saving time on the road seemed more natural than shaving off a few miles by traveling on smaller streets.

We then had to put the trips together into a 99-stop tour. This is not so easy.

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.

The traveling-salesman problem is one of the great unsolved problems in mathematics, capturing notions of complexity that are at the core of the information age.

Using deep theory developed in the 1960s, an efficient method for solving the T.S.P. would provide an efficient method for solving any computational problem for which it is easy to verify that an answer is correct. Most mathematicians expect this to be impossible, but no one knows for sure.

The first person to settle the issue, one way or the other, will pick up a $1,000,000 prize.

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.

Saving time on the road can be useful for a candidate, but a bigger payoff can come from combining optimal routing with the selection of campaign stops. In the final days before the caucuses, candidates must be choosy about where they invest the last hours of their campaigns. As much as the candidates would like to attend events wherever they have support, they simply cannot be everywhere at once.

Campaign managers must estimate the impact of meeting the crew at Pizza Ranch in Mount Pleasant versus holding a meeting at the Ivy Bake Shoppe in Fort Madison. And of course in planning a final whirlwind tour, you want to hold the events that you hope will yield the biggest gains in the polls.

But it also takes time to travel from one event to another, so a pair of events in nearby cities might have more impact than a single event in a larger city that happens to be on the other side of the state. So how many of the high-impact events can you squeeze into the tour?

An answer can be provided by a variant of the T.S.P. known as the prize-collecting traveling salesman problem.

In this version, there is a prize associated with each city, and the problem is to pick up the most valuable prizes in the remaining time available. The solution selects the cities where events should be held, the order in which the events should be placed into a schedule and the city-to-city travel directions.

It might not win the election, but an optimal solution can give a candidate a fighting chance.

Current politics can make any scientifically minded person want to tear out her hair, but it can also lead to pretty mathematics. So let’s hope for the best come Election Day. And if you want a break from day-to-day political news, and who doesn’t, you can always pick up a Ticonderoga No.2, put down your Sudoku and go to work on the traveling salesman problem yourself.

William Cook is a professor of industrial and systems engineering at Georgia Tech and the author of “In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation,” which is coming out in January.

 LMatrix:  Об автобусном туре Обамы можно прочесть здесь:

http://lmatrix.ru/news/reviews/obama-otpravilsya-v-predvybornyjj-tur-na-super-avtobuse-za-1-1-mln_243.html

Дополнительный материал на тему:

P vs NP Problem

Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

http://www.claymath.org/millennium/P_vs_NP/