Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems

被引：5

作者：

David Applegate

Robert Bixby

Vašek Chvátal

William Cook

机构：

[1] Algorithms and Optimization Department,

[2] AT&T Labs – Research,undefined

[3] Florham Park,undefined

[4] NJ 07932,undefined

[5] USA,undefined

[6] Computational and Applied Mathematics,undefined

[7] Rice University,undefined

[8] Houston,undefined

[9] TX 77005,undefined

[10] USA,undefined

[11] Department of Computer Science,undefined

[12] Rutgers University,undefined

[13] Piscataway,undefined

[14] NJ 08854,undefined

[15] USA,undefined

[16] Industrial and Systems Engineering,undefined

[17] Georgia Institute of Technology,undefined

[18] Atlanta,undefined

[19] GA 30332,undefined

[20] USA,undefined

来源：

Mathematical Programming | 2003年 / 97卷

关键词：

Combinatorial Optimization; Integer Programming; Broad Classis; Travel Salesman Problem;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

Dantzig, Fulkerson, and Johnson (1954) introduced the cutting-plane method as a means of attacking the traveling salesman problem; this method has been applied to broad classes of problems in combinatorial optimization and integer programming. In this paper we discuss an implementation of Dantzig et al.'s method that is suitable for TSP instances having 1,000,000 or more cities. Our aim is to use the study of the TSP as a step towards understanding the applicability and limits of the general cutting-plane method in large-scale applications.

引用

页码：91 / 153

页数：62