
Accession Number : ADA019798
Title : A Comparison of Two Different Lagrangean Relaxations of the Traveling Salesman Problem.
Descriptive Note : Technical rept.,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Smith,T. H. C. ; Thompson,G. L.
Report Date : NOV 1975
Pagination or Media Count : 23
Abstract : The authors propose a new Lagrangean relaxation of the traveling salesman problem and indicate how Srinivasan and Thompson's area cost operator theory of parametric programming for the transportation problem may be used to obtain a set of Lagrangean multipliers for which the Lagrangean relaxation provides a better lower bound on the minimum tour cost than the well known assignment lower bound. Computational experience with this approach is discussed which shows that the lower bounds obtained are significantly better than the assignment lower bound in the symmetric case while in the asymmetric case only a small improvement is obtained. However, it was found that the computational benefit obtained from using this improved lower bound in the subtour elimination algorithm for the traveling salesman problem did not justify its computational cost.
Descriptors : *Mathematical programming, Lagrangian functions, Computations, Costs, Algorithms
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE