CRPC-TR98744						July 1998

Title: On the Solution of Traveling Salesman Problems

Authors: David Applegate, Robert Bixby, William Cook, and Vasek Chvatal

Submitted July 1998

Abstract:
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 TSP instances with more than several hundred cities; over the
years, it has evolved further through the work of M. Grotschel, S. Hong,
M. Junger, P. Miliotis, D. Naddef, M. Padberg, W.R. Pulleyblank, G.
Reinelt, G. Rinaldi, and others. We enumerate some of its refinements that
led to the solution of a 13,509-city instance.

-------------------------------------------------------------------------------
David Applegate		Robert Bixby		William Cook
davida@caam.rice.edu	bixby@caam.rice.edu	bico@caam.rice.edu
Department of Computational and Applied Mathematics
Rice University

Vasek Chvatal
chvatal@rashers.rutgers.edu
Department of Computer Science
Rutgers University