The Traveling Salesm- um, -thingamajig

On Brandon's weblog Siris, a discussion of a science fiction premise of absolute access to history prompted me, ever the literalist, to refer to the Traveling Salesman Problem. Brandon suggested that I write a post on it. It's taken me two weeks, but I'm finally getting around to it. I've dressed the problem up a bit to give it some zest, but I haven't changed the essence of the problem, nor the solutions.

The Traveling Salesman Problem is a classical problem of Discrete Mathematics with huge repercussions in areas that are important to modern commerce, including computer science. The problem is so classical that we still refer to it as the Traveling Salesman Problem and no one takes offense even though the "Traffic Navigation Problem" or the "Traveling Sales Rep Problem" or even the "Traveling Salesthingamajig Problem" would be more gender equitable. At least, no one was taking offense the last time I checked! If the reader does feel alarm, I trust you will take comfort when you see further down that Mr. Traveling Salesman reports to Ms. CEO.

The basic idea goes something like this. A salesman wants to visit companies in five different cities, leaving from and ending in his hometown, A. Likewise, we'll call the other towns B, C, D, E, and F. If these letters make you uncomfortable, just think of them as shorthand for Alberta, Birmingham, Caskaloosa, Dunwiddy, Elenia, and Florencia. See? this is a real world problem!

Obviously, the salesman doesn't want to visit the same city twice. The Travel Manager at The Company has given him a list of prices for each route from one city to another, as illustrated in the graph below. You should see that travel from city A to city B has a cost of 1, while to travel from city A to city F has a cost of 20. (This is still a real-world problem! Travel from Alberta to Birmingham costs $100, while travel from Alberta to Florencia costs $2000.)

(Someone looking at this graph may find the numbers contrived. Yes, they are! But so are real-world airfares, as I wrote about earlier this year after obtaining tickets for Russia.)

The Company wants to spend as little money as possible on the trip. The travel manager spent some time figuring a low-cost route, and arrived at 39 (we'll see how in a moment). The Company has offered a 50% bonus to the Traveling Salesman if he can find a less expensive route.* The Traveling Salesman wants as big a bonus as possible, so he's willing to spend a little time and effort to find a cheaper route than the travel manager did. So he calls up his local university and asks for a mathematician, or at least a computer scientist. Why? Because what follows is a short and, hopefully, accurate summary of what you can find in any textbook for a class usually listed as something like "Contemporary Mathematics" but really ought to be called "Mathematics for People Who Are Terrified of Mathematics so They Chose a Major That Doesn't Require Any But Then They Saw That They Have to Satisfy a Liberal Arts Requirement" but which more than makes up in accuracy what it lacks in brevity.**

Method One: BRUTE FORCE
Summary: Study all possible cases.

Details in the example: In the picture above, there are 120 possible cases. Why? Starting from point A, the salesman has 5 choices for a city to visit. Suppose he chooses D. After that, the salesman will have 4 choices for a city to visit: B, C, E, F. After that, 3 choices. and so on, until he has to return to A. This gives us 5×4×3×2×1 = 120 possible routes.***

I'm too lazy to sit down and calculate all 120 routes, and I don't think you want to read all those details anyway, so I won't tell you the answer. If you have the time and interest, it can be done, but don't expect a bonus from me. I ain't The Company. I will give a hint for setting up:

1. all 120 routes start with A, and all 120 end with A;
2. 24 have B as their second letter, 24 have C as their second letter, 24 have D, 24 have E, and 24 have F;
3. finish each route using the remaining letters, making sure you don't write earlier routes backwards when you're trying to figure out the later routes. (This little mistake can really dog you).

The Good: The Brute Force method finds the correct answer. Guaranteed. If the Traveling Salesman does this carefully, he will manage a sweet bonus of at least 10 from The Company, because even lazy ol' me has found a route that costs 19. (You'll see how below.)

The Bad: Time is money, and going through all 120 routes takes time. What's worse, real-world applications of the Traveling Salesman Problem involve graphs that have a lot more than 6 points. Lots more. Once the graph has 20 points, there are 20×19×18×...×2×1 = an incomprehensibly large number of routes. (121, 645, 100, 408, 832, 000 to be precise, but you probably didn't want to know that.) It would take even a supercomputer a while to work it out. A few more points than that (I forget the exact number) and it's way too many even for a computer to compute before the end of the universe.

The Ugly: This kind of multiplication is called factorial, and mathematicians hate factorials. They show up in state lotteries, too, which helps explain why it's stupid to play the lottery, although lotteries are set up to divide out a lot of the factorial using other factorials. Otherwise, no one would ever win, and then no one would ever play.****

The Verdict: You can't use the Brute Force method to solve real-world Traveling Salesman problems. Our protagonist needs another method.

Method 2: Nearest Neighbor
Summary: At any point, take the least expensive route to another city.

Details in the example: Start from A. Pick the path that costs least, and travel to that city. In the graph above, that sends us to B, because at 1 it's by far the least expensive route from A. Then pick the path that costs least from B, which in our case presents us with a choice between C or D. Here, you can pick whichever route you like. I'll randomly choose C, but I've checked D and going that way doesn't help much. Continuing in this fashion, we end up circling around the figure (A-B-C-D-E-F-A), obtaining a total cost of 39. Notice that this is how the Travel Manager obtained his estimate.

The Good: This method is fast, fast, fast! In many graphs, it does well at finding a low-cost solution, although you can't count on its being the lowest cost.

The Bad: It is easy to find a graph where this method finds an abysmally expensive solution: to wit, the graph above.

The Ugly: See The Bad.

The Verdict: The Traveling Salesman wants a bonus, so we need something better.

Method 3: the Cheapest Link
Summary: (1) Pick the cheapest link in the graph. (2) Repeat (1) until done, avoiding looping or joining three links at one city.

Details in the example: For us, that would (again) start with A-B, at a cost of 1. After that, we have a choice of A-E, B-C, B-D, D-E, each of which has a cost of 2. We can choose three of them without visiting a city twice. I chose A-E, B-C, and D-E. Experimenting with different combinations might give better results. After these three, we have no choice but to travel the routes C-F (costs 6) and D-F (costs 15) to complete the graph; there are no other possibilities. The total cost is 28, substantially lower than the Travel Manager's choice. In this case, the Traveling Salesman would earn a bonus of 5, or maybe 6 if The Company felt like being generous and rounding up.

The Good: This method is fast, fast! In graphs like the one above, it provides substantially better results than the Nearest Neighbor method.

The Bad: Like the Nearest Neighbor method, this method does not often produce the cheapest result; the graph above will prove an example of this. What's worse, one can produce graphs where the Nearest Neighbor method finds better results than the Cheapest Link method.

The Ugly: If the graph is sufficiently large, it can take a while to sort the links from least expensive to most expensive.

Method 4: Repeated Nearest Neighbor
Summary: Sometimes, doing a stupid thing several times can give a good result. The Traveling Salesman should apply Nearest Neighbor several times, starting once at each city. He chooses the route that costs least, then adjusts it so that he starts from A.

Details in the example: We computed above the Nearest Neighbor route starting from A. If we compute it starting from the other cities, we get (check & tell me if these are wrong)
    B-A-E-D-C-F-B at a cost of 19!!!
    C-B-A-E-D-F-C at a cost of 28... big deal
    D-B-A-E-C-F-D at a cost of 31... ugh
    E-A-B-D-C-F-E at a cost of 25... okay
    F-B-A-E-D-C-F at a cost of 19!!!
At this point things are looking great. Why bother trying any harder? We can rewrite the route B-A-E-D-C-F-B as A-E-D-C-F-B-A and it still costs only 19.

Ms. CEO will be delighted to reward the Traveling Salesman with a bonus of 10, since the company saves 10 over the Travel Manager's suggestion, a savings of nearly 25%.

The Good: This method is easy and relatively fast. It will certainly give no worse a result than only one application of Nearest Neighbor.

The Bad: It still doesn't always find the lowest cost solution. Cheapest Link is sometimes better.

The Ugly: Well, it is more complicated than Nearest Neighbor, after all. In our example, it required 6 cities × 4 decisions/city = 24 decisions. (Remember that the last 2 links are always forced, so you can't decide them: you have to travel to the last city before returning home.) In a graph with 20 points, you would check 20 routes, which means 20×18 = 360 decisions, substantially more than the 18 decisions necessary for Nearest Neighbor or Cheapest Link. Of course, for the Cheapest Link you first have to sort those 20 points, but that doesn't have to take long; a good sorting algorithm will get it done quickly.

The Verdict: Always a good method to try, but reserve some skepticism.

Summary: No one knows how to obtain the best result without Brute Force. This is true in a lot of mathematics actually: one makes an art of approximating the truth as precisely as possible.

There are probably other algorithms out there, too. Once when teaching this class I experimented with a "Reverse Cheapest Link" method, where I kept throwing out the most expensive links until I had a route. That didn't help much, and in fact I think I extraordinarily badly on some graphs. When writing this up, I experimented with starting from the two cheapest routes out of a city, then removing the most expensive links from the overedetermined graph I had created, without isolating a city. In this example, from A I chose A-B and A-E; from B I then chose B-C and B-D (as I had already chosen the least expensive, A-B, and B-C and B-D tied); and so forth. I ended up with A-B-F-C-D-E-A, at a cost of 19. Okay, no surprise. I'm sure I could come up with an example where this fails.

In the context of the original discussion on Brandon's weblog: the implications for "absolute access to all history" are hopefully obvious. Even if you had absolute access to all historical information, you could not possibly process all of it from every point of view.

*This isn't in the original problem, but things like this ought to happen in real life.

**Really! Most of the stuff in "Contemporary" Mathematics consists of fairly old results. Like, centuries old. Okay, so it's not as old as algebra perhaps, or even calculus, but it's certainly older than a lot of Number Theory, Abstract Algebra, or Statistics, and definitely older than Gröbner bases. The miracle is that these ancient problems, often formulated by people who really had too much time on their hands—residents of Königsberg, I'm talking about you, even if now you're called Kaliningrad—is enormously useful in modern applications of mathematics. But you won't hear about that because mathematics is supposed to be boring, and "old" math is supposed to be even more boring, and we can't interrupt everyone's tidy view of the world, now, can we?

*** Notice that we multiplied 5, 4, 3, 2, and 1, instead of adding them. Why? For EACH choice of the first city, the salesman has 4 choices for the second. For EACH choice of the second city, he has 3 choices for the third, etc. "EACH" translates to multiplication, the same way that buying 10 hamburgers which EACH costs $2 means that you're out $20 = $2×10 and in for a lot of cholesterol.

**** Curiously, state lotteries are usually advertised on the premise of improving education, which is ludicrous because anyone who has enough education to understand how lotteries work, and the near-certain probability of losing, won't play often enough to support the public education system. And that's before the state legislature decides to reduce the general fund's support of education because, after all, education is now getting lottery money, and we have other priorities too! (This happened in North Carolina while I was a graduate student there, and Virginia did something similar when I was younger.) But no one listens to me.