In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation

"The title refers to the travelling salesman problem (TSP), which is the problem of working out the shortest route that visits a specified group of cities and then returns to the starting point. The problem gets its name from the travelling salesman who wants to visit all the target cities while minimising the total distance he or she travels. It sounds like a very narrow problem but actually, as the author shows very clearly, there are many instances where it arises and it’s very important to solve it. For example, suppose you’re looking at the night sky with a telescope and you want to visit a certain number of stars. In what order do you move between the stars to minimise the movement of the telescope and its wear and tear? Similarly, when you’re laying out computer chips: how do you move the device—that’s coming down on that chip and plonking things on the circuit—to make the process as fast as possible? No. First of all, the problem is very hard. Even with the fastest computers and the best algorithms that we have today, we aren’t able to solve it yet. We can’t find the best route in any reasonable time, except for a small number of cities. More interestingly, from the mathematical point of view, despite the intense efforts of mathematicians and computer scientists, we don’t even know how to quantify how hard the problem is, in a technical sense. In maths, we’re always trying to say: here’s a problem, here’s some measure of the difficulty of it. We don’t really know how difficult this problem is. We don’t know where to put it in the hierarchy from easy problems to almost insoluble problems. Is it just that we haven’t thought of the best algorithm or is it that there is no efficient algorithm for solving it? Well, in a sense, this is how the problem is solved at the moment, with heuristics. A salesman might think he or she has got a good route but it may still be far from optimal. How would they know? Of course, the more cities there are—we’re talking here about a few hundred cities—the harder it becomes to know whether you’ve found anything like the best route. There’s a long history of development of algorithms, each building on the previous one, from the 1960s onwards. The original statement of the problem goes back to the 18th century, with Euler and Hamilton, but it was really only with the advent of computers that people started to make any headway. The 1950s onwards, I would say, is when it started to become a real area of research. This book is by one of the leading researchers on the TSP and gives a very readable and wide-ranging treatment of the problem. Before reading it, I hadn’t realized just how widespread the TSP problem is. Cook also has a fascinating discussion of various heuristics that have been proposed for TSP over the years. These are illustrated with lots of helpful diagrams. The subtitle is ‘Mathematics at the Limits of Computation’ and it does an excellent job of explaining how large TSPs are tackled, harnessing the best available algorithms with the fastest computers. First of all, I should say what it means to solve the problem. We’ve been talking about the very best solution. That is what’s hard. What the algorithms available at the moment will do is offer approximations. They will give upper and lower bounds. So, they’ll say, if you want to do a 1000 city travelling salesman tour of this group of cities, then here’s a tour that I can guarantee is within 5% of the best. In practical terms, that’s probably okay, it’s enough. The mathematical difficulty is in saying how hard the problem is, and giving the very best route. That’s what people in this research area try to do. Large amounts of computer time are being spent trying to tackle this problem. There’s also the possibility that a completely new idea will come along and revolutionise the field. This has happened in other areas of mathematics: a famous conjecture gets solved with a completely new approach. This may be one area where that might happen. Yes, that’s the framework that I was referring to, the ‘P versus NP’ problem, which is one of the seven Clay Institute Millennium Problems, for each of which a $1 million prize is available for a solution."