On the solution of traveling salesman problems (Q1126862): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Property / author | |||
| Property / author: David L. Applegate / rank | |||
| Property / author | |||
| Property / author: Vašek Chvátal / rank | |||
| Property / author | |||
| Property / author: David L. Applegate / rank | |||
Normal rank | |||
| Property / author | |||
| Property / author: Vašek Chvátal / rank | |||
Normal rank | |||
| Property / describes a project that uses | |||
| Property / describes a project that uses: TSPLIB / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| links / mardi / name | links / mardi / name | ||
Latest revision as of 02:17, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the solution of traveling salesman problems |
scientific article |
Statements
On the solution of traveling salesman problems (English)
0 references
6 August 1998
0 references
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.
0 references
traveling salesman
0 references
cutting planes
0 references
