Accession Number : ADA019799

Title :   A Computational Comparison of an Improved Pair Assignment Algorithm and a Pair Exclusion Algorithm for the Quadratic Assignment Problem.

Descriptive Note : Technical rept.,

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

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

Report Date : NOV 1975

Pagination or Media Count : 25

Abstract : The author proposes (and also tests computationally) a pair assignment algorithm and a pair exclusion algorithm for the quadratic assignment problem (QAP) also known as the problem of assigning facilities to locations. The linear assignment problem relaxation of the QAP (intorduced by Land and Gavett and Plyter) is used and the pair assignment algorithm is essentially the same as that of Gavett and Plyter except that the optimal solution of the linear assignment problem is obtained at each subproblem in the tree search. The pair exclusion algorithm is based on the algorithm presented by Pierce and Crowston.

Descriptors :   *Nonlinear programming, *Integer programming, Search theory, Computations, FORTRAN, Algorithms

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE