In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation
4/5
()
About this ebook
The story of one of the greatest unsolved problems in mathematics
What is the shortest possible route for a traveling salesman seeking to visit each city on a list exactly once and return to his city of origin? It sounds simple enough, yet the traveling salesman problem is one of the most intensely studied puzzles in applied mathematics—and it has defied solution to this day. In this book, William Cook takes readers on a mathematical excursion, picking up the salesman's trail in the 1800s when Irish mathematician W. R. Hamilton first defined the problem, and venturing to the furthest limits of today’s state-of-the-art attempts to solve it. He also explores its many important applications, from genome sequencing and designing computer processors to arranging music and hunting for planets.
In Pursuit of the Traveling Salesman travels to the very threshold of our understanding about the nature of complexity, and challenges you yourself to discover the solution to this captivating mathematical problem.
Some images inside the book are unavailable due to digital copyright restrictions.
William J. Cook
William J. Cook is professor of combinatorics and optimization at the University of Waterloo. He is the coauthor of The Traveling Salesman Problem: A Computational Study (Princeton).
Read more from William J. Cook
Princeton Series in Applied Mathematics
Related to In Pursuit of the Traveling Salesman
Related ebooks
The Golden Ticket: P, NP, and the Search for the Impossible Rating: 4 out of 5 stars4/5Digital Dice: Computational Solutions to Practical Probability Problems Rating: 5 out of 5 stars5/5Why Do Buses Come in Threes: The Hidden Mathematics of Everyday Life Rating: 3 out of 5 stars3/5The Fascinating World of Graph Theory Rating: 4 out of 5 stars4/5A Passion for Mathematics: Numbers, Puzzles, Madness, Religion, and the Quest for Reality Rating: 4 out of 5 stars4/5Life By the Numbers Rating: 4 out of 5 stars4/5Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers Rating: 0 out of 5 stars0 ratingsGuesstimation 2.0: Solving Today's Problems on the Back of a Napkin Rating: 4 out of 5 stars4/5The Traveling Salesman Problem: A Computational Study Rating: 5 out of 5 stars5/5Game, Set and Math: Enigmas and Conundrums Rating: 3 out of 5 stars3/5Millions, Billions, Zillions: Defending Yourself in a World of Too Many Numbers Rating: 4 out of 5 stars4/5An Imaginary Tale: The Story of √-1 Rating: 4 out of 5 stars4/5Fearless Symmetry: Exposing the Hidden Patterns of Numbers - New Edition Rating: 4 out of 5 stars4/5How Mathematicians Think: Using Ambiguity, Contradiction, and Paradox to Create Mathematics Rating: 4 out of 5 stars4/5The Best Writing on Mathematics 2018 Rating: 0 out of 5 stars0 ratingsThe Best Writing on Mathematics 2019 Rating: 0 out of 5 stars0 ratingsThe Best Writing on Mathematics 2017 Rating: 0 out of 5 stars0 ratingsGamma: Exploring Euler's Constant Rating: 4 out of 5 stars4/5e: The Story of a Number Rating: 4 out of 5 stars4/5Summing It Up: From One Plus One to Modern Number Theory Rating: 5 out of 5 stars5/5Duelling Idiots and Other Probability Puzzlers Rating: 4 out of 5 stars4/5In Pursuit of Zeta-3: The World's Most Mysterious Unsolved Math Problem Rating: 3 out of 5 stars3/5Calculus Reordered: A History of the Big Ideas Rating: 0 out of 5 stars0 ratingsElliptic Tales: Curves, Counting, and Number Theory Rating: 5 out of 5 stars5/5Mathematics and Plausible Reasoning, Volume 1: Induction and Analogy in Mathematics Rating: 0 out of 5 stars0 ratingsUncle Petros and Goldbach's Conjecture: A Novel of Mathematical Obsession Rating: 4 out of 5 stars4/5Number Theory: A Historical Approach Rating: 4 out of 5 stars4/5Reverse Mathematics: Proofs from the Inside Out Rating: 4 out of 5 stars4/5The Best Writing on Mathematics 2012 Rating: 4 out of 5 stars4/5Elements of Mathematics: From Euclid to Gödel Rating: 4 out of 5 stars4/5
Mathematics For You
My Best Mathematical and Logic Puzzles Rating: 4 out of 5 stars4/5Algebra II For Dummies Rating: 3 out of 5 stars3/5What If?: Serious Scientific Answers to Absurd Hypothetical Questions Rating: 5 out of 5 stars5/5Quantum Physics for Beginners Rating: 4 out of 5 stars4/5Calculus Made Easy Rating: 4 out of 5 stars4/5The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics Rating: 3 out of 5 stars3/5Algebra - The Very Basics Rating: 5 out of 5 stars5/5The Little Book of Mathematical Principles, Theories & Things Rating: 3 out of 5 stars3/5Relativity: The special and the general theory Rating: 5 out of 5 stars5/5Alan Turing: The Enigma: The Book That Inspired the Film The Imitation Game - Updated Edition Rating: 4 out of 5 stars4/5Painless Algebra Rating: 0 out of 5 stars0 ratingsBasic Math & Pre-Algebra For Dummies Rating: 4 out of 5 stars4/5GED® Math Test Tutor, 2nd Edition Rating: 0 out of 5 stars0 ratingsThe Joy Of X: A Guided Tour of Math, from One to Infinity Rating: 5 out of 5 stars5/5Standard Deviations: Flawed Assumptions, Tortured Data, and Other Ways to Lie with Statistics Rating: 4 out of 5 stars4/5Sneaky Math: A Graphic Primer with Projects Rating: 0 out of 5 stars0 ratingsLimitless Mind: Learn, Lead, and Live Without Barriers Rating: 4 out of 5 stars4/5The Golden Ratio: The Divine Beauty of Mathematics Rating: 5 out of 5 stars5/5Real Estate by the Numbers: A Complete Reference Guide to Deal Analysis Rating: 0 out of 5 stars0 ratingsHow Math Explains the World: A Guide to the Power of Numbers, from Car Repair to Modern Physics Rating: 3 out of 5 stars3/5Basic Math & Pre-Algebra Workbook For Dummies with Online Practice Rating: 4 out of 5 stars4/5Must Know High School Algebra Rating: 5 out of 5 stars5/5Mental Math: Tricks To Become A Human Calculator Rating: 5 out of 5 stars5/5The Math of Life and Death: 7 Mathematical Principles That Shape Our Lives Rating: 4 out of 5 stars4/5ACT Math & Science Prep: Includes 500+ Practice Questions Rating: 3 out of 5 stars3/5Flatland Rating: 4 out of 5 stars4/5
Reviews for In Pursuit of the Traveling Salesman
12 ratings0 reviews
Book preview
In Pursuit of the Traveling Salesman - William J. Cook
In Pursuit of the Traveling Salesman
In Pursuit of the Traveling Salesman
Mathematics at the Limits of Computation William J. Cook
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 OX20 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.
QA164.C69 2012
511’.5—dc23 2011030626
British Library Cataloging-in-Publication Data is available
This book has been composed in Minion
Printed on acid-free paper ∞
Typeset by S R Nova Pvt Ltd, Bangalore, India
Printed in the United States of America
10 9 8 7 6 5 4 3 2 1
Listen, mate, I’ve traveled every road in this here land.
—Geoff Mack, Lyrics to I’ve Been Everywhere.
Contents
Preface
1 Challenges
Tour of the United States
An Impossible Task?
One Problem at a Time
Road Map of the Book
2 Origins of the Problem
Before the Mathematicians
Euler and Hamilton
Vienna to Harvard to Princeton
And on to the RAND Corporation
A Statistical View
3 The Salesman in Action
Road Trips
Mapping Genomes
Aiming Telescopes, X-rays, and Lasers
Guiding Industrial Machines
Organizing Data
Tests for Microprocessors
Scheduling Jobs
And More
4 Searching for a Tour
The 48-States Problem
Growing Trees and Tours
Alterations While You Wait
Borrowing from Physics and Biology
The DIMACS Challenge
Tour Champions
5 Linear Programming
General-Purpose Model
The Simplex Algorithm
Two for the Price of One: LP Duality
The Degree LP Relaxation of the TSP
Eliminating Subtours
A Perfect Relaxation
Integer Programming
Operations Research
6 Cutting Planes
The Cutting-Plane Method
A Catalog of TSP Inequalities
The Separation Problem
Edmonds’s Glimpse of Heaven
Cutting Planes for Integer Programming
7 Branching
Breaking Up
The Search Party
Branch-and-bound for Integer Programming
8 Big Computing
World Records
The TSP on a Grand Scale
9 Complexity
A Model of Computation
The Campaign of Jack Edmonds
Cook’s Theorem and Karp’s List
State of the TSP
Do We Need Computers?
10 The Human Touch
Humans versus Computers
Tour-finding Strategies
The TSP in Neuroscience
Animals Solving the TSP
11 Aesthetics
Julian Lethbridge
Jordan Curves
Continuous Lines
Art and Mathematics
12 Pushing the Limits
Notes
Bibliography
Index
Preface
The star of Geoff Mack’s 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 Vašek Chvátal 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 aren’t 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 Mack’s 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 day’s 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 planet’s 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 bruteforce 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 Vašek Chvátal, 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.
il, 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, Günter 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.
In Pursuit of the Traveling Salesman
1: Challenges
It grew out of the trio’s efforts to find solutions for a classic mathematical problem—the Traveling Salesman
problem—which 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.
Police officers Toody and Muldoon navigated Car 54 in a popular American television series. Their 33-city task is an instance of the traveling salesman problem, or TSP for short. In its general form, we are given a collection of cities and the distance to travel between each pair of them. The problem is to find the shortest route to visit each city and to return to the starting point.
Is the general problem easy, hard, or impossible? The short answer is that no one really knows. This is both the mystery and attraction of this famous challenge in computational mathematics. And much more than a struggling salesman is at stake. The TSP is the focal point of a larger debate on the nature of complexity and possible limits to human knowledge. If you are ready for action, then a sharp pencil and a clean piece of paper are all you may need to give a helping hand to the salesman and possibly to make a quantum leap in our understanding of the world in which he or she travels.
Figure 1.1 Car 54 contest. Image courtesy of Procter & Gamble.
Tour of the United States
Despite its nasty reputation, the TSP is an easy enough task from one perspective: there are only finitely many possible routes through a given set of cities. So a 1962-era mathematician could have checked each possible Toody-Muldoon tour, recorded the shortest, sent the solution to Procter & Gamble, and waited for the $10,000 check to arrive in the mail. A simple and flawless strategy. With one possible catch. The number of distinct tours is exceedingly large to consider checking one by one.
This difficulty was noticed in 1930 by the Austrian mathematician and economist Karl Menger, who first brought the challenge of the TSP to the attention of the mathematics community. This problem is of course solvable by finitely many trials. Rules that give a number of trials below the number of permutations of the given points are not known.
² A tour can be specified by announcing the order in which the cities are to be visited. For example, if we label the 33 destinations of Toody and Muldoon as A through Z and 1 though 7, that is, A for Chicago, B for Wichita, etc., then we can record a possible tour as
ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567
or any other arrangement of the 33 symbols. Each such arrangement is a permutation of the symbols. The ordering implied by the arrangement is circular, in that we travel from the last city back to the first. So we can record the same tour in 33 ways, depending on which city we put in the first position. To avoid such overcounting, we may as well always start with city A. This leaves 32 choices for the second city, 31 choices for the third city, and so on. Altogether, we have 32 × 31 × 30 × … × 3 × 2 × 1 tours to consider. This is the total number of permutations of 32 objects. It is written as 32! and spoken as 32 factorial.
In the Procter & Gamble contest we can save effort by noting that the distance to travel between Chicago and Wichita is the same as the distance between Wichita and Chicago, and this is true also for every other pair of cities. With such symmetry it does not matter in which direction we travel around a tour, so an ordering
ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567
is the same as its reverse
7654321ZYXWVUTSRQPONMLKJIHGFEDCBA.
We can therefore cut down by half our count of the 33-city tours, leaving only 32!/2 orderings to check. Before you go ahead and get out your Ticonderoga #2 pencil, note that this is
131,565,418,466,846,765,083,609,006,080,000,000
distinct tours that we must examine.
These days we would of course employ a computer to run through the list. So let’s choose a big one, the $133,000,000 IBM Roadrunner Cluster of the United States Department of Energy. This 129,600-core machine topped the 2009 ranking of the 500 world’s fastest supercomputers, delivering up to 1,457 trillion arithmetic operations per second.³ Let’s assume we can arrange the search for tours such that examining each new one requires only a single arithmetic operation. We would then need roughly 28 trillion years to solve the 33-city TSP on the Roadrunner, an uncomfortable amount of time, given that the universe is estimated to be only 14 billion years old. No wonder Menger was unsatisfied with the brute-force solution to the problem.
When considering the implications of this quick analysis, we must keep in mind that Menger writes only that faster rules for solving the salesman problem are unknown, not that such rules are out of the question. John Little and coauthors sum this up nicely in the following comment on the Procter & Gamble contest. A number of people, perhaps a little over-educated, wrote the company that the problem was impossible—an interesting misinterpretation of the state of the art.
⁴ Little et al. went on to describe a breakthrough in TSP solution methods, but they could not push their computer codes far enough to actually solve the 33-city challenge. It appears that no one in the country was able to produce a route that could be guaranteed to be the shortest of all possible tours for Toody and Muldoon.
Figure 1.2 Drummer’s Delight. Newsweek, July 26, 1954, page 74.
The 33-city problem was definitely a tough nut to crack, but if we turn back the clock to 1954, then we find a team that almost certainly would be able to deliver the optimal route, together with a written guarantee that their solution is the shortest. The team tackled a larger touring problem through the United States, visiting a city in each of the 48 states, as well as Washington, D.C. This particular challenge had been circulating through the mathematics community since the mid-1930s. Its solution was reported in Newsweek.⁵
Finding the shortest route for a traveling salesman—starting from a given city, visiting each of a series of other cities, and then returning to his original point of departure—is more than an after-dinner teaser. For years it has baffled not only goods-and salesman-routing businessmen but mathematicians as well. If a drummer visits 50 cities, for example, he has 10⁶² (62 zeros) possible itineraries. No electronic computer in existence could sort out such a large number of routes and find the shortest.
Three Rand Corp. mathematicians, using Rand McNally road-map distances between the District of Columbia and major cities in each of the 48 states, have finally produced a solution. By an ingenious application of linear programming—a mathematical tool recently used to solve production-scheduling problems—it took only a few weeks for the California experts to calculate by hand
the shortest route to cover the 49 cities: 12,345 miles.
The California experts were George Dantzig, Ray Fulkerson, and Selmer Johnson, part of an exceptionally strong and influential center for the new field of mathematical programming, housed at the RAND Corporation in Santa Monica.
The RAND team’s guarantee involves some pretty mathematics that we take up later in the book. For now it is best to think of the guarantee as a proof, like those we learned in geometry class. The Dantzig et al. proof establishes that no tour through the 49 cities can have length less than 12,345 miles. Matching the proof with their tour of precisely this length shows that this particular instance of the TSP has been settled, once and for all.
Dantzig and company missed out on the $10,000 contest, but we can report that a computer implementation of their ideas makes easy work of the 33-city TSP. A shortest route for Toody and Muldoon is depicted in Figure 1.3. Although no one in 1962 knew for certain that this was the shortest possible tour, a number of contestants did find and report this same ordering. Among the people tied for first place in the contest were mathematicians Robert Karg and Gerald Thompson, who created a hit-or-miss heuristic strategy that produced the winning solution.⁶ And the story has a happy ending, at least for the mathematics community. As a tiebreaker, contestants were asked to write a short essay on the virtues of one of Procter & Gamble’s products. Thompson’s prose on soaps took a grand prize.
Figure 1.3 Optimal tour for Car 54 contest.
An Impossible Task?
The RAND team’s work put an end to the 48-states challenge, but it did not finish off the TSP. One big success did not imply the team could handle other, possibly larger, instances of the problem. In fact, if Las Vegas were taking bets on the outcome, the odds-on favorite among mathematicians would be that we will never fully solve the TSP. We must be careful here. By a solution we mean an algorithm, that is, a step-by-step recipe for producing an optimal tour for any example we may throw at it. Just finding the best route through the United States or any other country does not do the job.
Picking up on the expected difficulty of the general TSP challenge, the science-fiction story Antibodies
, by Charles Stross, chronicles doomsday events following the discovery of an efficient solution method for the salesman.⁷ One can hope that a brilliant insight into the TSP will not signal the end of the world as we know it, but it will certainly turn the planet upside down and give it a good shake. To see why, let’s start with a series of quotes.
‘It seems very likely that quite a different approach from any yet used may be required for successful treatment of the problem. In fact, there may well be no general method for treating the problem and impossibility results would also be valuable.’
—Merrill Flood, 1956.⁸
‘I conjecture that there is no good algorithm for the traveling salesman problem.’
—Jack Edmonds, 1967.⁹
‘In this paper we give theorems which strongly suggest, but do not imply, that these problems, as well as many others, will remain intractable perpetually.’
—Richard Karp, 1972.¹⁰
The authors of these remarks are three giants of traveling-salesman research. Merrill Flood rallied support for the problem in the 1940s; more than anyone else, Flood is responsible for the emergence of the TSP as a fundamental topic of study. Discussing the state of the problem in 1956, Flood first raised the possibility that efficient methods may simply never exist. This point was hammered home by Jack Edmonds a decade later in what amounts to a mathematical bet against the hope for a general solution method. Edmonds was modest in describing the support for his bet: My reasons are the same as for any mathematical conjecture: (1) It is a legitimate mathematical possibility, and (2) I do not know.
But he is teasing us with these words: Edmonds is one of the profound thinkers in twentieth-century mathematics and he certainly had something deep in mind when placing money against the TSP. Five years later, the true nature of the bet was made clear in a publication by the great computer scientist Richard Karp, connecting the TSP with a host of other computational problems. We save the details of Karp’s theory for chapter 9, but a quick account will be enough to understand why the characters of Antibodies
shuddered at the announcement of a fast TSP algorithm.
Good and Bad Algorithms
When Edmonds writes good algorithm,
he uses the word good in the same way as you and I: an algorithm is good if it can solve problems in an amount of time we find acceptable. For this to make sense in mathematics, however, he had to make good
into a formal notion. Clearly, we cannot expect every example of the TSP to be solved, say, in under a minute by a human or by one of our machines. We must at least be willing to allow