ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

17. Control Theory and Optimization

1991 MS Classification: 90C10 90C27 Cook, William, Rice University, USA The Traveling Salesman Problem

In 1954, G. Dantzig, R. Fulkerson, and S. Johnson demonstrated that large instances of the TSP could be solved using the duality theory of linear programming. Their work was inspired by the theoretical studies of J. Robinson and H. Kuhn in the late 1940s and the early 1950s, and it remains the only known method for solving TSP instances having more than several hundred cities. We discuss the evolution of their methodology, including the research of M. Grötschel, S. Hong, M. Padberg and others. The techniques will be illustrated on the solution of a 13,509-city example. This talk is based on joint work with David Applegate, Robert Bixby, and Vašek Chvátal.

ICM 1998 Berlin · Plenary and Invited Lectures