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

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

0.00 Avg rating0 Votes
Article ID: iaor20041851
Country: Germany
Volume: 97
Issue: 1/2
Start Page Number: 91
End Page Number: 153
Publication Date: Jan 2003
Journal: Mathematical Programming
Authors: , , ,
Keywords: cutting plane algorithms
Abstract:

Dantzig, Fulkerson, and Johnson 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.

Reviews

Required fields are marked *. Your email address will not be published.