Professor William Cook delivered an MAA invited address at the Joint Mathematics Meeting in San Diego on January 11. The title of his presentation was Information, Computation, Optimization: Connecting the Dots in the Traveling Salesman Problem. The presentation can be viewed here.
Abstract: Few math models scream impossible as loudly as the traveling salesman problem. Given n cities, the TSP asks for the shortest route to take you to all of them. Easy to state, but if P≠NP then no solution method can have good asymptotic performance as n goes off to infinity. The popular interpretation is that we simply cannot solve realistic examples. But this skips over nearly 70 years of intense mathematical study. Indeed, in 1949 Julia Robinson described the TSP challenge in practical terms: "Since there are only a finite number of paths to consider, the problem consists in finding a method for picking out the optimal path when n is moderately large, say n=50." She went on to propose a linear programming attack that was adopted by her RAND colleagues Dantzig, Fulkerson, and Johnson several years later.
Following in the footsteps of these giants, we use linear programming to show that a certain tour of 49,603 historic sites in the US is shortest possible, measuring distance with point-to-point walking routes obtained from Google Maps. We highlight aspects of the modern study of polyhedral combinatorics and discrete optimization that make the computation feasible. This is joint work with Daniel Espinoza, Marcos Goycoolea, and Keld Helsgaun.