Article ID: | iaor199016 |
Country: | United States |
Volume: | 37 |
Issue: | 5 |
Start Page Number: | 760 |
End Page Number: | 768 |
Publication Date: | Sep 1989 |
Journal: | Operations Research |
Authors: | Christofides Nicos, Benavent E. |
Keywords: | networks |
The Tree QAP is a special case of the Quadratic Assignment Problem (QAP) where the nonzero flows form a tree. No condition is required for the distance matrix. This problem is NP-complete and is also a generalization of the Traveling Salesman Problem. In this paper, we present a branch-and-bound algorithm for the exact solution of the Tree QAP based on an integer programming formulation of the problem. The bounds are computed using a Lagrangian relaxation of this formulation. To solve the relaxed problem, the authors present a Dynamic Programming algorithm which is polynomially bounded. The obtained lower bound is very sharp and equals the optimum in many cases. This fact allows the authors to employ a reduction method to decrease the number of variables and leads to search-trees with a small number of nodes compared to those usually encountered in problems of this type. Computational results are given for problems with size up to 25.