William J Cook - In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation

In Pursuit of the Traveling Salesman

Mathematics at the Limits of Computation

William J. Cook

PRINCETON UNIVERSITY PRESS

Princeton and Oxford

Copyright 2012 by Princeton University Press

Published by Princeton University Press, 41 William Street,

Princeton, New Jersey 08540

In the United Kingdom: Princeton University Press, 6 Oxford Street,

Woodstock, Oxfordshire 0X20 1TW press.princeton.edu

All Rights Reserved

Library of Congress Cataloging-in-Publication

Data Cook, William, 1957

In pursuit of the traveling salesman: mathematics at the limits of computation/William J. Cook. p. cm.

Includes bibliographical references and index.

ISBN 978-0-691-15270-7 (hardback)

1. Traveling salesman problem. 2. Computational complexity. I. Title.

British Library Cataloging-in-Publication Data is available

Listen, mate, I've traveled every road in this here land.

Geoff Mack, Lyrics to "I've Been Everywhere."

Contents

The star of Geoff Macks song has been to Reno, Chicago, Fargo, Buffalo, Toronto, Winslow, Sarasota, Wichita, Tulsa, Ottawa, Oklahoma, Tampa, Panama, Mattawa, LaPaloma, Bangor, Baltimore, Salvador, Amarillo, Tocapillo, Barranquilla, and Padilla.

One night in February 1988, my friend Vaek Chvtal and I decided to follow in the footsteps of mathematical giants and take a crack at finding the shortest way around such destinations. Next day we met at Tri-State Camera, a computer vendor in lower Manhattan. When the technician learned we were mathematicians in need of a speedy computer, he looked us in the eye and warned, You guys arent trying to solve that traveling salesman problem, are ya?" Quite a bit of foresight there. This was the first of many computers we ground to a halt, spending the better part of the next twenty years searching for solutions.

The notorious problem is to compute the shortest route to visit each city on a specified list and return to the starting point. In the case of Geoff Macks traveler, one could conceivably check all 51,090,942,171,709,440,000 tours through the twenty-two cities. This computation would require even the fastest of supercomputers to roll up its sleeves and prepare for a hard days work, but with patience it may be possible to carry out the search. If, however, we had one hundred cities or so, then checking all routes to select the shortest is out of the question, even devoting the entire planets computing resources to the task.

This observation on sorting through all possible solutions is by no means a convincing argument that the salesman problem is actually difficult. There are similar problems that are very easy to solve and yet have far more candidate solutions than the number of ways to route a salesman. What sets the traveling salesman problem apart is the fact that despite decades of research by top applied mathematicians around the world, in general it is not known how to significantly improve upon simple brute- force checking. It is a real possibility that there may never exist an efficient method that is guaranteed to solve every example of the problem. This is a deep mathematical question: is there an efficient solution method or not? The topic goes to the core of complexity theory concerning the limits of feasible computation. For the stouthearted who would like to tackle the general version of the problem, the Clay Mathematics Institute will hand over a $1,000,000 prize to anyone who can either produce an efficient method or prove that this is impossible.

The complexity question that is the subject of the Clay Prize is the Holy Grail of traveling-salesman-problem research and we may be far from seeing its resolution. But this is not to say mathematicians have thus far come away empty-handed. Indeed, the problem has led to a large number of results and conjectures that are both beautiful and deep. In the arena of exact computation, an 85,900-city challenge problem was solved in 2006, when the optimal tour was pulled out of a mind-boggling number of candidates in a computation that took the equivalent of 136 years on top- of-the-line computer workstations. On the practical side, solution methods are used to compute optimal or near-optimal tours for a host of applied models on a daily basis.

One of the enduring strengths of the traveling salesman problem has been its remarkable success as an engine of discovery in applied mathematics and its fields of operations research and mathematical programming. And many more discoveries could be waiting just around the corner. A primary goal of the book is to stimulate readers to pursue their own ideas for the solution of this mathematical challenge.

In setting down these notes I have had the pleasure of receiving help and support from many people. First of all, I thank my comrades David Applegate, Robert Bixby, and Vaek Chvtal, for over twenty years of fun and work toward unraveling part of the traveling salesman mystery. I also thank Michel Balinsky, Mark Baruch, Robert Bland, Sylvia Boyd, William Cunningham, Michel Goemans, Timothy Gowers, Nick Harvey, Keld Helsgaun, Alan Hoffman, David Johnson, Richard Karp, Mitchel Keller, Anton Kleywegt, Bernhard Korte, Harold Kuhn, Jan Karel Lenstra, George Nemhauser, Gary Parker, William Pulleyblank, Andre Rohe, Lex Schrijver, Bruce Shepherd, Stan Wagon, David Shmoys, Gerhard Woeginger, and Phil Wolfe for discussions of the problem and its history.

Images and historical material used in the presentation were provided by Hernan Abeledo, Leonard Adleman, David Applegate, Masashi Aono, Jessie Brainerd, Robert Bixby, Adrian Bondy, Robert Bosch, John Bartholdi, Nicos Christofides, Sharlee Climer, James Dalgety, Todd Eckdahl, Daniel Espinoza, Greg Fasshauer, Lisa Fleischer, Philip Galanter, Brett Gibson, Marcos Goycoolea, Martin Grtschel, Merle Fulkerson Guthrie, Nick Harvey, Keld Helsgaun, Olaf Holland, Thomas Isrealsen, David Johnson, Michael Jnger, Brian Kernighan, Brbel Klaaen, Bernhard Korte, Drew Krause, Harold Kuhn, Pamela Walker Laird, Ailsa Land, Julian Lethbridge, Adam Letchford, Panagiotis Miliotis, J. Eric Morales, Randall Munroe, Yuichi Nagata, Denis Naddef, Jaroslav Neetil, Manfred Padberg, Elias Pampalk, Rochelle Pluth, Ina Prinz, William Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, Ron Schreck, va Tardos, Mukund Thapa, Michael Trick, Marc Uetz, Yushi Uno, Gnter Wallner, Jan Wiener, and Uwe Zimmermann. I thank them all for their kindness.

This book was written in the great environments of the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Tech and the Department of Operations Research and Financial Engineering at Princeton University. My work on the traveling salesman problem is funded by grants from the National Science Foundation (CMMI-0726370) and the Office of Naval Research (N00014-09-1-0048), and by a generous endowment from A. Russel Chandler III. I am grateful for their continued support.

Finally, I thank my family, Monika, Benny, and Linda, for years of patiently listening to salesman stories.

It grew out of the trio's efforts to find solutions for a classic mathematical problemthe "Traveling Salesman" problemwhich has long defied solution by man, or by the fastest computers he uses.

IBM Press Release, 1964.

An advertising campaign by Procter & Gamble caused a stir among applied mathematicians in the spring of 1962. The campaign featured a contest with a $10,000 prize. Enough to purchase a house at the time. From the official rules:

Imagine that Toody and Muldoon want to drive around the country and visit each of the 33 locations represented by dots on the contest map, and that in doing so, they want to travel the shortest possible route. You should plan a route for them from location to location which will result in the shortest total mileage from Chicago, Illinois back to Chicago, Illinois.