Linear programming is a fundamental course in every operations research curriculum. The implication of including a course on linear models at the core of our discipline is that linearity is realistic for many applications. Bill Cook addresses this big assumption  in his book In Pursuit of the Traveling Salesman, which features an important moment in operations research history at the University of Wisconsin-Madison.

News of the general linear-programming model, and the simplex algorithm for its solution, was delivered by George Dantzig in 1948 at a meeting held at the University of Wisconsin. The event was a defining moment for Dantzig, who has described often its proceedings. Like many good stories, repeated telling may have shifted a few details over the years, but all versions capture the spirit of a nervous rising star facing a large and distinguished group of mathematicians and economists. During the discussion following Dantzig’s lecture, Harold Hotelling, great in both academic stature and physical size, rose from his seat, stated simply, “But we all know the world is nonlinear,” and sat down. Dantzig was lost for a reply to such a sweeping criticism.

Suddenly another hand in the audience was raised. It was John von Neumann. “Mr. Chairman, Mr. Chairman,” he said, “if the speaker does not mind, I would like to reply for him.” Naturally I agreed. von Neumann said: “The speaker titled his talk ‘linear programming’ and carefully stated his axioms. If you have an application that satisfies the axioms, well use it. If it does not, then don’t.”

Fortunately for the world, many of its complexities can in fact be described in sufficient detail by linear models. The episode with Dantzig, Hotelling, and John von Neumann is summed up nicely by a cartoon Dantzig’s colleagues reported as hanging outside his office. It featured the Peanuts character Linus in his traditional pose, sucking his thumb and holding a blanket. The caption read, “Happiness is assuming the world is linear.”

HT to Jeff Linderoth for reminding me to blog about this.

Related reading:

• your ideal summer beach read: In Pursuit of the Traveling Salesman Problem
• the TSP for cheeseheads

On Monday, Professor Bill Cook, Professor in Combinatorics and Optimization at the University of Waterloo gave the Hilldale Lecture at the University of Wisconsin. See my earlier blog post about this here.

Bill’s talk on the Traveling Salesman Problem (“One NP-hard problem to rule them all“) was terrific! Bill is a master multi-tasker as evidence by how he effortlessly controlled his talk on three separate screens by three iPhones that he carried around his talk (one was strapped to his wrist).

Bill gave a great overview talk about the TSP. He talked about the history of the TSP and the main contributions, the intuition problem behind proving tours are optimal using linear programming duality and why cutting planes are helpful, and why heuristics work so well, and challenges for parallelizing the algorithms. I highly encourage reading Bill Cook’s book In Pursuit of the Traveling Salesman to learn more.

Fun TSP fact: One of the early mentions of the TSP was made by a report by Julia Robinson of the RAND Corporation in 1949, who published On the Hamiltonian game (a traveling salesman problem) [Link].

Another fun TSP fact: More recently, a woman started a 50 first dates quest via Kickstarter, where she would have a date in each of the lower 48 states plus DC and Canada [Link]. She will tour the cities and make a documentary about it. (Side note: She will probably talk about her dates more than about math in the documentary – I bet she won’t even mention cutting planes once!)

In 2012 Bill ran a TSP challenge that boasted a winning prize of $500 for finding the best tour in a 115,475-city challenge through (nearly) all cities, towns, and villages in the contiguous 48 states. [Link]. The three best tours all independently found different tours of the same length. A good approach for finding a near-optimal tour in a big TSP instance is to use a combination of local search and genetic algorithms. Local search tweaks part of a tour to make it slightly better. Genetic algorithms mix different tours to take good partial tours from two potential solutions to (potentially) find a better tour that combines their best parts. The combination is powerful. Bill has a few new TSP challenges and it sounds like he’ll buy you a beer if you solve them. Another fun fact: If you want a bigger prize, The Clay Institute offers a $1 million prize for finding a polynomial time algorithm for solving TSP.

Bill mentioned that fast computers helped to solve hard TSP instances but not for the reason that you might think. The fast computers and processors we have now are more accessible than the supercomputers that were used in early TSP research. Now we can tinker with computer algorithms on a laptop (or phone), and this helps to reduce the feedback loop in research, and the faster feedback is helpful for driving good research (more so than the fast computing itself).  I am young enough that I was surprised by one  of Bill’s comments about a 1987 TSP algorithm that took 23 hours on a supercomputer, “We were all surprised they were allowed to use that much computing time.” Time has certainly changed.

Bill ended the talk by hinting at future research directions including time travel and parallelization. Recently, there have been some publications that suggest that monkeys [Link] and bees [Link] solve TSP instances. But Bill was skeptical that monkeys will assist us with the next TSP algorithm breakthrough.

A tour from Newsweek published on July 26, 1954

Bucky the Badger is ready to tour Wisconsin!

This TSP blog post is in honor of Bill Cook’s lecture at the University of Wisconsin on Monday, April 7:

HF Deluca Forum

The Discovery Building.

12 – 1 pm.

More info: go.wisc.edu/salesman.

We are very excited to host Bill on Monday. Bill informally launched an information Dairyland TSP challenge on twitter, a tour through all 165 stops in America’s Dairyland [link to pdf]. What is the shortest tour? Hint: try using Bill’s TSP iPhone/iPad app!

For more reading:

• Bill has some fantastic TSP resources on his web site.
• My colleague Jordan Ellenberg’s reviewed In Pursuit of the Traveling Salesman in the Wall Street Journal.
• Here is my review of In Pursuit of the Traveling Salesman.
• How to visit all 30 Major League Baseball stadiums in the shortest amount of time.
• A Christmas brain teaser (yes, it involves the TSP)

Here are a few other TSP links.

xkcd on the TSP

A TSP genetic algorithm that finds a tour of the lower 48 state capitals. Courtesy of MathGifs

This video shows a visualization of Greedy, Local Search, and Simulated Annealing strategies for solving 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