Main navigation | Main content

HOME » PROGRAMS/ACTIVITIES » Public Lectures

PROGRAMS/ACTIVITIES

Annual Thematic Program »Postdoctoral Fellowships »Hot Topics and Special »Public Lectures »New Directions »PI Programs »Math Modeling »Seminars »Be an Organizer »Annual »Hot Topics »PI Summer »PI Conference »Applying to Participate »

IMA PUBLIC LECTURE

The Traveling Salesman Problem

The Traveling Salesman Problem

2002-2003 Program: Optimization

**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

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.

Computational
Methods for Large Scale Integer Programs, *October 14-19,
2002*