A LIFO Implicit Enumeration Search Algorithm for the Symmetric Traveling Salesman Problem using Held and Karp's 1-Tree Relaxation.
Abstract
It is proposed here a LIFO implicit enumeration search algorithm for the symmetric traveling salesman problem which uses the 1-tree relaxation of Held and Karp. The proposed algorithm has significantly smaller memory requirements than Held and Karp's branch-and-bound algorithm. Computational experience with this algorithm and an improved version of Held and Karp's algorithm is reported and on the basis of the sample it can be stated that the proposed algorithm is faster and generates many fewer subproblems than Held and Karp's algorithm. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1975
- Accession Number
- ADA019546
Entities
People
- Gerald L. Thompson
- T. H. C. Smith
Organizations
- Carnegie Mellon University