William J. Cook
PRINCETON UNIVERSITY PRESS 2012, 228 PAGES
PRICE £19.95 (HARDBACK) ISBN 978-0-691-15270-7
In Pursuit of the Traveling Salesman gives a very readable account of progress in tackling one of the most important problems in Applied Mathematics: the Travelling Salesman Problem. The problem of finding the shortest route through a number of cities is finite and therefore solvable in principle but becomes disproportionately complex as this number grows. Theoretical, practical and historical aspects of the problem are thoroughly explained.
The opening chapter Challenges details the problem including two examples of competitions with cash prizes. The Proctor & Gamble competition in 1962 offered $10,000 for the shortest route visiting 33 locations in the USA. A more academic competition concerns degrees of complexity. P is the class of problems which can be solved in polynomial time. NP is the class of problems for which a solution can be verified in polynomial time. The Clay Institute $1,000,000 prize challenge is to prove one way or the other whether P and NP are identical. TSP belongs in NP (in fact it is called NP-complete as every NP problem can be reduced to the TSP) and it has been proved that if an algorithm is found that can solve TSP in polynomial time this would in turn prove that P=NP.
Further chapters explore wide-ranging of aspects of TSP including the fascinating origins of TSP and related problems such as the Bridges of Königsberg and Hamiltonian circuits. The earliest recognisable TSP example is cited in a German salesman’s book of 1832. Applications of TSP far removed from a physical journey between cities demonstrate its versatility, such as guiding industrial machines, drilling circuit boards and mapping genomes, but the nodes of these networks are still referred to as ‘cities’.
A number of approaches are considered, including sophisticated techniques from Artificial Intelligence such as hill-climbing, genetic algorithms and inspiration from ant colonies. Search techniques which explore and gradually limit the solution space, such as branch-and-bound, are explored. Two chapters are devoted to a strong exposition of Linear Programming using Dantzig’s Simplex solution and the formulation of TSP as an integer LP problem. A chapter on Big Computing looks at large-scale problems tackled with a combination of advanced hardware, algorithmic engineering and mathematical techniques. The extreme example is the optimal movement of a telescope to observe over 500 million celestial objects.
There is a detailed study of Complexity and the nature of algorithms, and their relationship to practical computing; but also techniques that transcend computation as we know it. A comment that “Turing-style computing is by no means the only tool” (p.184) is questionable: even the exotic devices suggested (DNA in microbes, Optics and Quantum effects) are surely subject to the Church-Turing thesis. One fanciful exception is a time machine to send solutions from the future! Other off-beat approaches are explored which go beyond calculation, including naïve intuition of adults and children and inspiration from the animal kingdom: chimpanzees and pigeons picking up food from several locations. A chapter on Aesthetics shows examples of abstract art inspired by TSP solutions, pleasant to the eye but for reasons unclear. Whether such artistic insight could in turn be useful in finding solutions could be asked.
The final chapter, Pushing the Limits, looks at how the TSP might develop in the future considering alternative scenarios where P=NP or otherwise. More could be written about the possibility that P=NP is not Gödel-decidable. A rallying cry for readers is to ‘bash on regardless’.
There is some overlap between the chapters. Connections with nature appear in several guises: live chimpanzees, simulated ant colonies and DNA in microbes. These could be brought together. Similarly issues of psychology arise in several places.
This book covers all facets of the TSP and ventures into some very deep theory of complexity and computability. It is written for the general mathematician or scientist but would also be useful to the OR specialist. Overall it is entertaining, richly illustrated and well-referenced. It tells us much about general problem solving as well as the TSP.
Francis McGonigal CMath MIMA
Birmingham City University
