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

摘要

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.