Created 11/7/99; Last Updated 11/7/99
11:00 AM-12:00 PM
Room: Gold Rush A
TSPLIB is Gerhard Reinelt's library of some hundred instances of the traveling salesman problem. Some of these instances arise from the task of drilling holes in printed circuit boards; others arise in X-ray crystallography; yet others have been constructed artificially. None of them (with a single exception) is contrived to be hard and none of them is contrived to be easy; their sizes range from 17 to 85,900 cities; some of them have been solved and others have not.
Following the theoretical studies of J.B. Robinson and H.W. Kuhn in the late 1940s and the early 1950s, G.B. Dantzig, R. Fulkerson, and S.M. Johnson demonstrated in 1954 that large instances of the TSP could be solved by linear programming. Their approach remains the only known tool for solving nontrivial TSP instances with more than several hundred cities; over the years, it has evolved further through the work of M.Grötschel, S. Hong, M. Jünger, P. Miliotis, D. Naddef, M. Padberg, W.R. Pulleyblank, G. Reinelt, G. Rinaldi, and others.
We enumerate some of its refinements that allowed us to solve more than twenty previously unsolved instances from the TSPLIB. One of these is the instance with 225 cities, ts225, that was contrived to be hard; the sizes of the others range from 1,000 to 13,509 cities.
This is joint work with D. Applegate, R. Bixby, and W. Cook.
V. Chvátal
Rutgers University