Accession Number : ADA019798

Title :   A Comparison of Two Different Lagrangean Relaxations of the Traveling Salesman Problem.

Descriptive Note : Technical rept.,

Corporate Author : CARNEGIE-MELLON 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