Geodesic
On the solution of traveling salesman problems
Documenta mathematica, ICM Berlin 1998, Vol. III (1998), pp. 645-656.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

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. 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 led to the solution of a 13,509-city instance.
Classification : 90C35, 90C10, 90C27
Keywords: traveling salesman, cutting planes 
@article{DOCMA_1998__S9__a16,
     author = {Applegate, David and Bixby, Robert and Chv\'atal, Va\v{s}ek and Cook, William},
     title = {On the solution of traveling salesman problems},
     journal = {Documenta mathematica},
     pages = {645--656},
     publisher = {mathdoc},
     volume = {ICM Berlin 1998, Vol. III},
     year = {1998},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DOCMA_1998__S9__a16/}
}
TY  - JOUR
AU  - Applegate, David
AU  - Bixby, Robert
AU  - Chvátal, Vašek
AU  - Cook, William
TI  - On the solution of traveling salesman problems
JO  - Documenta mathematica
PY  - 1998
SP  - 645
EP  - 656
VL  - ICM Berlin 1998, Vol. III
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DOCMA_1998__S9__a16/
LA  - en
ID  - DOCMA_1998__S9__a16
ER  - 
%0 Journal Article
%A Applegate, David
%A Bixby, Robert
%A Chvátal, Vašek
%A Cook, William
%T On the solution of traveling salesman problems
%J Documenta mathematica
%D 1998
%P 645-656
%V ICM Berlin 1998, Vol. III
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DOCMA_1998__S9__a16/
%G en
%F DOCMA_1998__S9__a16
Applegate, David; Bixby, Robert; Chvátal, Vašek; Cook, William. On the solution of traveling salesman problems. Documenta mathematica, ICM Berlin 1998, Vol. III (1998), pp. 645-656. http://geodesic.mathdoc.fr/item/DOCMA_1998__S9__a16/