Accession Number : ADA019546
Title : A LIFO Implicit Enumeration Search Algorithm for the Symmetric Traveling Salesman Problem using Held and Karp's 1-Tree Relaxation.
Descriptive Note : Research rept. Feb-Jul 75,
Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Smith,T. H. C. ; Thompson,G. L.
Report Date : JUL 1975
Pagination or Media Count : 33
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)
Descriptors : *Operations research, *Mathematical programming, *Algorithms, *Hamiltonian, Search theory, Problem solving, Heuristic methods
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE