Bill Cook’s TSP talk at the University of Wisconsin-Madison

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