A LIFO Implicit Enumeration Search Algorithm for the Symmetric Traveling Salesman Problem using Held and Karp's 1-Tree Relaxation.

摘要

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)