Accession Number : ADA019800

Title :   A LIFO Implicit Enumeration Algorithm for the Asymmetric Traveling Salesman Problem Using a One-Arborescence Relaxation.

Descriptive Note : Technical rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Smith,Theunis H. C.

Report Date : OCT 1975

Pagination or Media Count : 22

Abstract : The author proposes a LIFO implicit enumeration algorithm for the asymmetric traveling salesman problem in which the one-arborescence relaxation of the traveling salesman problem (originally suggested by Held and Karp) is employed as a fathoming device. The efficient Edmonds-Fulkerson algorithm is used to construct minimum-cost arborescences. Computational exerpience with the algorithm is also presented.

Descriptors :   *Integer programming, Mathematical models, Algorithms, Computations, FORTRAN

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE