On the solution of traveling salesman problems
type: Item
instance of: scholarly article
title: On the solution of traveling salesman problems
zbMATH Open document ID: 0904.90165
author: Robert E. Bixby
author: William Cook
author: David Applegate
author: Vašek Chvátal
published in: Documenta Mathematica
publication date: 1998-08-06T00:00:00Z
full work available at URL: https://eudml.org/doc/233207
full work available at URL: Cook.MAN.html
review text: Summary: 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.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 1184401
zbMATH Keywords: traveling salesman
zbMATH Keywords: cutting planes
describes a project that uses: TSPLIB
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1184401