In Pursuit of the Traveling Salesman: Mathematics at the Limit of Computation
“In Pursuit of the Traveling Salesman describes the problem of creating the most efficient solution to computing the shortest travel route—visiting each city on a list and returning to the start. If you are curious about the TSP, this book will give you way more information about it than you could possibly ever want to know, but you will also gain general insight into the algorithms, complexity, and limits of computation. . . . a thoroughly entertaining nerd-fest for the science-minded reader.”
Finding efficient routes is important not just to salesmen but to anyone who travels or tours for a living, not just school bus drivers, or meals-on-wheels drivers or authors on book tours but all those who travel for inspections or logistics, for industry or for science.
The need for creating an efficient route comes up in a variety of scientific fields including genetics and astronomy. In computer science and manufacturing the Traveling Salesman Problem (TSP) shows up in computationally driven tasks such as determining efficient routes in drilling and soldering printed circuit boards, in data organization, and in job scheduling.
In Pursuit of the Traveling Salesman describes the problem of creating the most efficient solution to computing the shortest travel route—visiting each city on a list and returning to the start. If you are curious about the TSP, this book will give you way more information about it than you could possibly ever want to know, but you will also gain general insight into the algorithms, complexity, and limits of computation.
TSP as an interesting problem was first defined by W. R. Hamilton in the 1800s but only identified as of interest to mathematicians by Karl Menger in 1930, who brought it to the attention of the mathematics community. The grandfather of TSP was perhaps Leonhard Euler who studied the seven bridges of Konigsberg in 1735 in the search for a perfectly efficient tour (which was impossible).
The Traveling Salesman Problem is easy to explain but can be difficult to solve, especially regarding an efficient tour for more than a few cities. For even 20 randomly placed cities, the number of distinct routes to compare is too large to check by hand.
A brute force algorithm can take a very long for a computer, too. For example, a tour of 33 cities, if solved by brute force (the distance to every city compared against to every other city) on a supercomputer running at 1 and 1/2 teraflops, (where a teraflop is 10 raised to the 12th floating point operations per second) would take 28 trillion years complete. Consider that the universe is only 14 billion or so years old!
The brute force algorithm is a bad algorithm for solving the TSP, however there are better algorithms than brute force. The difference between a good and a bad algorithm is that a good algorithm will complete in a reasonable amount of time, while a bad algorithm may never (realistically) complete. The detail of the difference between a good algorithm and a bad algorithm is in scaling, how the number of steps in the algorithm scale with the number of data elements in the problem (where in this case the data elements are the number of cities).
A good algorithm is expressed in what mathematicians call “deterministic polynomial” time, for example N raised to a constant power (where N is the number of elements) is a deterministic time polynomial, and is a good algorithm. Bad algorithms are expressed in the number of steps that contains any variable or constant raised to the Nth power. Mathematicians and computer scientists call good algorithms “P” for polynomial time, and bad algorithms, “NP” for non-deterministic time polynomial.
The algorithm used in brute forcing an efficient tour of N cities takes (N-1)!/2 steps, which is bad because of the N factorial part, (factorial means N times N-1 times N-2, times N -3, . . . ). The best algorithm to date is the Held Karp algorithm, discovered in 1962, where the number of steps is proportional to 2 raised to the N times N-squared, and although this is the best algorithm it is still bad because of that pesky 2 raised to the N part.
The larger debate is one on the nature of complexity and the limits of human creativity in its ability to tame that complexity. Is it possible to find a good algorithm of polynomial time for the TSP, or is TSP now and forever non-deterministic? The answer is open and the argument (and does) cuts both ways among mathematicians.
That the efficient solution to the TSP is a deep and important mathematical question is recognized by the Clay Mathematics Institute (CMI) in their offering of a $1 million prize for either identifying a more efficient, i.e. “P” method or by proving that an efficient method is impossible, i.e. that NP != P.
There are also contests for solving tours of increasing numbers of cities. The first contest was held was in 1954 and had 49 cities, and was (necessarily) solved by computer. The best year for TSP solutions was 1987 when tours of 532, 666, 1002, and 2392 cities were solved. A map with 85,900 cities was solved in 2006. In this case the number of cities represented not cities but holes to be drilled by a laser for manufacturing a custom computer chip. The current DIMACS World Challenge is for a greater than 1-million city tour created in 2001 that has yet to be solved.
The author, William Cook, writes in an easy to understand style and explores the various algorithms and branches of mathematics used to solve TSP, including the branch of mathematics known as linear programming, which is known to most of us through grade school algebra and word problems.
One of the most famous algorithms in the whole world history of algorithms is the Simplex algorithm, which is used in linear programming and was discovered by George Dantzig in 1948. The name Simplex in this instance doesn’t mean simple but refers to a classical geometrical object, for example a 2D simplex is a triangle, and a 3D simplex is a tetrahedron. The Simplex algorithm although tremendously useful, has the same failing as the best algorithm in TSP. The Simplex algorithm also has no guarantee of having a deterministic polynomial running time.
One drawback of linear programming in the real world is that it provides fractional solutions where whole numbers may be more useful. Mr. Cook goes on to identify the branch of linear programming that provides whole number solutions, called integer programming (IP). “IP solvers” have been put to practical use in decision-making in business, for example in determining whether is more cost effective to make N number of widgets of type X versus M number of widgets of type Y, given a set of resources. The name for an organization that solves this kind of manufacturing problem is called “Operations Research.”
Many algorithms over the past decades have been explored in attempts to improve the efficiency of TSP routes. Explorations of these algorithms lead to the ability to solve tours of greater numbers of cities (albeit without solving the underlying question). Many of these algorithms have interesting names, for example, “nearest neighbor”, “greedy”, “spanning trees,” “hill climbing,” “simulated annealing heuristics,” “space filling curves,” “genetic algorithms,” and “ant-colony optimizations.”
One possible solution for TSP may be an algorithm that uses massive amounts of parallelism. An experiment using parallelism has been made by coding the DNA of bacteria, but to date this has only solved a very small (three city) example.
Another possible solution is to exploit the massive parallelism of light using optical computing, but again the technical issues still need to be worked out. Similarly the technical issues with quantum computers are also yet to be resolved.
In the end chapters, William Cook addresses to the nature of complexity, the mechanics of computation itself and the aesthetics of TSP routes. Topics include Turing machines, NP- completeness, satisfiability, and artwork inspired by TSP.
Do these explorations and possibilities of potential lead to a proof one way or another? Maybe. Maybe not.
In Pursuit of the Traveling Salesman also provides illustrations for those who like pictures with their algorithms. Included are maps of city tours, routes used by salesmen and by lawyers (including Lincoln’s tour with the Illinois circuit court in 1850), and photos of mathematicians. One photo (without explanation) is of the author presenting a chamber pot to J. P. Donleavy, the author of The Ginger Man.
In Pursuit of the Traveling Salesman is a thoroughly entertaining nerd-fest for the science minded reader.