your ideal summer beach read: In Pursuit of the Traveling Salesman Problem

If you haven’t read Bill Cook’s In Pursuit of the Traveling Salesman, I highly recommend it as the perfect summer beach read. I am way overdue for a review of this book, so this post is for those of you who haven’t read this book yet. I recommend Mike Trick’s reviews of this book on his blog and on Amazon. Instead of rehashing all the reasons why you should read the book, I will offer my reasons for why it is a fun summer beach read.

Bill’s writing style is engaging and fun. The book doesn’t overstay its welcome. Bill gets into enough detail about each topic so that the reader can appreciate the contribution or historical tidbit while not feeling like a chore (my first two requirements for summer vacation reading, which are rarely achieved by non-fiction books about science and technology).  The historical aspects of actual traveling salesman was fascinating. I enjoyed the part about Abraham Lincoln’s tour through central Illinois when he worked the Eighth Judicial Circuit as a lawyer (you’ll have to read the book to find out if this tour was optimal).

I found the chapter on TSP approximation algorithms and heuristics to be downright exciting. Every algorithm dominated for awhile until better algorithms emerged. I was familiar with some of the algorithms but not the entire tapestry of TSP algorithms, so I eagerly turned the pages until I reached the state of the art. The chapters on linear and integer programming might be a little tough for the average reader (meaning no OR/optimization/CS/math background), but the remaining chapters are accessible to a audience of general science readers.

There are a lot of great pictures in the book, and I believe the pictures are a big reason why it is so enjoyable to read. I suspect that many potential readers enjoy looking at maps, and there is no shortage of maps with TSP tours here. Often, I could look at a tour and see if the tour was “good” or not, and I could visualize how heuristics worked. I applaud Bill’s effort in putting together such great illustrations. This is an advantage for the TSP, since other optimization problems may not be able to draw from such a rich set of visuals as the TSP can.  In addition to the TSP maps, there are pictures of historic documents from actual traveling salesmen, TSP researchers (I liked the 1970s era pictures), and Robert Bosch’s beautiful TSP art. You would not want an audiobook of this book (and indeed, none is available).

In Pursuit of the Traveling Salesman is a labor of love about an important optimization problem. I feel indebted to Bill Cook for writing a book that makes optimization seem so thrilling to non-optimizers (I’m not sure I succeed at that very often on this blog). I highly recommend this book.

PS. Bill, thanks for the shout out (reference 32 in Chapter 5).

TSP at the beach