2002-2003 Program: Optimization

IMA PUBLIC LECTURE

The Traveling Salesman Problem

William J. Cook
Industrial and Systems Engineering
Georgia Institute of Technology
wcook@isye.gatech.edu
http://www.isye.gatech.edu/~wcook/

Wednesday, October 16, 2002, 7:00 PM

Moos Tower, Room 2-650
University of Minnesota, East Bank

Poster (pdf 6MB)    (jpg 211KB)
http://www.math.princeton.edu/tsp/

Talk 58 mins. Lecture Video (flv)|RealAudio(SureStream)

USA 13509 Cities

USA 13509 Maze

USA 13509 Tour

The traveling salesman problem, or TSP for short, is easy to state: given a number of "cities" along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities and returning to your starting point. The simplicity of the statement is deceptive - the TSP is one of the most intensely studied problems in computational mathematics and yet no effective solution method is known for the general case. Indeed, the resolution of the TSP would settle the P versus NP problem and fetch a $1,000,000 prize from the Clay Mathematics Institute.

Although the complexity of the TSP is still unknown, for over 50 years its study has led the way to improved solution methods in many areas of mathematical optimization. We will discuss the history of the TSP and examine the role it has played in modern computational mathematics. We will also present a collection of TSP applications, ranging from genome sequencing to on-line grocery shopping. Finally, we will present a survey of recent progress in algorithms for large-scale TSP instances, including the solution of a million-city instance to within 0.09% of optimality and the exact solution of a 15,112-city instance.

This talk is based on joint work with David Applegate, Robert Bixby, and Vasek Chvátal. It is partially supported by the Institute of Technology Alumni Society.

2002-2003 Program: Optimization