Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems |
| |
| Authors: | David Applegate Robert Bixby Va?ek Chvátal William Cook |
| |
| Institution: | (1) Algorithms and Optimization Department, AT&T Labs – Research, Florham Park, NJ 07932, USA, US;(2) Computational and Applied Mathematics, Rice University, Houston, TX 77005, USA, US;(3) Department of Computer Science, Rutgers University, Piscataway, NJ 08854, USA, US;(4) Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA, US |
| |
| Abstract: | 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.
Received: December 6, 2002 / Accepted: April 24, 2003
Published online: May 28, 2003
RID="*"
ID="*" Supported by ONR Grant N00014-03-1-0040 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
