The Traveling Salesman Problem: A Blueprint for Optimization

Dr. Karen Ames Memorial Lectures on Applied Mathematics

Dr. William Cook

Chandler Family Chair and Professor
Industrial and Systems Engineering
Adjunct Professor with Mathematics
Georgia Institute of Technology


13 January 2012

Shelby Center 109
3:00 (Refreshements at 2:30)

Abstract

Given a list of cities along with the cost of travel between each pair of them, the traveling salesman problem is to find the cheapest way to visit them all and return to your starting point. Easy to state, but difficult to solve. In this talk we discuss the problem's history, applications, and computation, laying out a blueprint for future work in optimization and the practical solution of large-scale, possibly intractable, decision models.

colloq CookBiographical Sketch

Dr. William Cook is the Chandler Family Chair in the School of Industrial and Systems Engineering at Georgia Tech. He received his Ph.D. in Combinatorics and Optimization from the University of Waterloo in 1983. Dr. Cook spent two years as an Alexander von Humboldt Research Fellow at the University of Bonn, and he has held positions at Cornell, Columbia, Bellcore, Rice, and Princeton.

Dr. Cook was elected a SIAM Fellow in 2009, an INFORMS Fellow in 2010, and a member of the National Academy of Engineering in 2011. Together with David Applegate, Robert Bixby, and Vasek Chvatal, he was awarded the 2007 Lanchester Prize by INFORMS for the book The Traveling Salesman Problem: A Computational Study.

Dr. Cook has delivered numerous invited and plenary lectures, including an invited lecture at the International Congress of Mathematicians in 1998, the I. E. Block Community Lecture at the SIAM Annual Meeting in 2003, and the SIAM Invited Lecture at the Joint Mathematics Meetings in 2011. He is a former Editor-in-Chief of Mathematical Programming (Series A and Series B), and he is the current Editor- in-Chief of the new journal Mathematical Programming Computation.