Solving the World's Hardest Problems

Last year, The New York Times reported that UPS managed to save 3 million gallons of gas in 2006 by altering the routes of delivery trucks to avoid left turns. According to them, the company uses software called "package flow" to map out daily routes for drivers.

Clearly, the method or "algorithm" this software employs to design efficient routes has sizeable economic (and greenhouse gas) consequences. And, not only is it far from perfect, but the general routing problem is so difficult that, well, if in the course of reading this article you happen upon an efficient solution, you will become immediately famous, at least among computer scientists.

Latest Videos From

Watch full video here:

The famous 19th century Irish mathematician Sir William Rowan Hamilton, who at age 12 once defeated the notorious American "calculating boy" Zerah Colburn in an arithmetic-off, invented the "Icosian game," in which players attempt to find round-trip routes through a twelve-sided figure such that each vertex is visited exactly once and no edge is visited twice (Regarding the spin-off "Traveler's Dodecahedron," the puzzle museum website states, "the rules have been simplified and made much more attractive than the original." The puzzle museum also notes that the Icosian game is more of a puzzle than a game.)

In 1972, UC Berkeley Professor Richard Karp published perhaps the most famous paper written to date in computer science, called "Reducibility Among Combinatorial Problems." The point, broadly speaking, is that most problems that appear difficult to solve exactly most likely are. Rather than proving that all kinds of problems have no easy solution, Karp gave a clever method for showing that many different sorts of problems are equivalent in a certain sense: if you provide a magic fast solver for hard problem A, Karp uses it to build a fast solver for hard problem B.

To understand what this means for the salesman, consider: A TSP with 5 cities has 12 possible routes; with 10 cities there are 181,440 possibilities; with 61 cities there are more possible paths than there are atoms in the universe. Seriously. In computer science terms, the solution space is exponential — adding one city roughly doubles the number of possible paths. Karp's result suggests that in general, determining the optimal path for the salesman is a matter of checking all those possibilities — though shortcuts may exist, none are likely to lift the exponential burden. And though computers are growing more powerful, even IBM's supercomputer, Blue Gene, which can perform a ridiculous 500 thousand billion computations per second, would have little hope of solving a 30-city TSP by the brute-force approach.

Instead, computer scientists spend much time devising heuristics — approximate methods for dealing with intractable situations. Here's a simple heuristic for the traveling salesman: when trying to decide which stop to visit next on the tour, pick the closest remaining one. While in many cases, this rule yields a route much less efficient than the optimal one, it works reasonably well on average. Many papers have been written about more complex heuristics for the TSP. For example, in 1997 Marco Dirigo used a simulated ant colony to explore the space of solutions, iteratively refining paths left by virtual ants (virtual pheromones were also involved).