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
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE