A Love Letter to the Traveling Salesman Problem

Bill Cook of Georgia Tech has a new book out on the Traveling Salesman Problem entitled “In Pursuit of the Traveling Salesman” from Princeton University Press (or from Amazon or B&N).  Unlike his previous book (with David Applegate, Bob Bixby and Vašek Chvátal), this book is aimed at a general audience. Bill takes his readers down a beautiful path covering the history, applications, and algorithms associated with the TSP. It is a fascinating story, and one that shows a researcher who truly loves his research area. You would think such a love was  common among researchers, but I have seen many researchers who seem bored by, or positively hate, their research areas. Bill is obviously enraptured by the TSP.

The Traveling Salesman Problem is remarkable easy to state:  given a set of points with distances between them, find the shortest tour through all the points.  For example, as Bill wrote about recently, given 99 towns in Iowa to visit and the road distances between every pair, what is the quickest way to see all the cities, returning to your starting position?

Despite its simple statement, the problem of finding good or optimal tours has generated thousands of research papers.  The TSP is the standard testbed for discrete optimization:  practically every possible approach to optimization can be tried out on the TSP.  So research on the TSP has had a tremendous effect on approaches for all sorts of other optimization problems.  Bill covers every aspect of this research corpus.

Perhaps the most interesting part about this book is that Bill pulls no punches when it comes to presenting work. Most of us would be tempted to go only so deep into an area and then start hand-waving believing “well, no one would understand this area anyway”. Here is how Bill begins a description of finding comb inequalities, a type of constraint necessary to determine the TSP polytope:

Subtour-elimination constraints? No problem. Comb inequalities? Not so good.
At the moment there is no known polynomial-time algorithm that is guaranteed to
spot a violated comb inequality if one exists. The comb-separation problem is also
not known to be in the NP-complete complexity class, so its status is wide open.
A great need coupled with inconclusive results translates into an important research
problem.

This is not to say that combs are currently skipped over in computations. By
hook or by crook computer codes must generate combs to push LP bounds after
subtour-elimination constraints fail. This is accomplished by hit-or-miss strategies
for growing handles, shrinking teeth, splicing sets, and a host of other operations.

If I tried to write this book, I don’t think I would have even got to comb inequalities, let alone continued to the nice description Bill provides of comb-finding heuristics.  This level of discussion requires some concentration when reading but the book is accessible to a wide audience.  This is an ideal book to get a college student or a smart high school student interested in operations research and combinatorial optimization.

This is a highly personal look at the TSP. Bill tells you his favorite heuristic (farthest insertion), his favorite exotic computing model (time traveling solver: take as long as you like to solve but then go back in time to report the solution), and much more.

Chapters have interesting lead quotes (the book begins with Listen, mate, I’ve traveled every road in this here land. from Geoff Mack in the song “I’ve Been Everywhere”), and the illustrations throughout are fantastic.  I also love the way that Bill includes pictures of practically everyone who has done research in this area. Putting faces to the names is a wonderful way to personalize the research.

Through this book, you’ll learn all about the Traveling Salesman Problem and, more broadly, about the different research directions in combinatorial optimization. And you’ll also see why top-notch researchers like Bill Cook find the TSP endlessly fascinating. And you might just want to be a researcher like Bill.

I guess a bit of a disclaimer is needed here: Bill has included a very nice mention of this blog in the book (thanks Bill!) with a picture of me,  and his publisher sent me an advance copy of the book. I failed miserably in getting a nice quote in on time, but that is due to my own failings. I really love the book!