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

被引：80

作者：

Applegate, D

Bixby, R

Chvátal, V

Cook, W

机构：

[1] AT&T Labs Res, Algorithms & Optimizat Dept, Florham Pk, NJ 07932 USA

[2] Rice Univ, Houston, TX 77005 USA

[3] Rutgers State Univ, Dept Comp Sci, Piscataway, NJ 08854 USA

[4] Georgia Inst Technol, Ind Syst Engn, Atlanta, GA 30332 USA

来源：

MATHEMATICAL PROGRAMMING | 2003年 / 97卷 / 1-2期

关键词：

FENCHEL CUTTING PLANES; EFFICIENT SEPARATION; COMB INEQUALITIES; LIN-KERNIGHAN; ROUTINES; FACET;

D O I：

10.1007/s10107-003-0440-4

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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

页数：63

共 64 条

[1] A fast and scalable radiation hybrid map construction and integration strategy [J].