A Comparison of Two Different Lagrangean Relaxations of the Traveling Salesman Problem.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1975
- Accession Number
- ADA019798
Entities
People
- Gerald L. Thompson
- T. H. C. Smith
Organizations
- Carnegie Mellon University