An Exact Algorithm for the Quadratic Assignment Problem on a Tree

Nicos Christofides and Enrique Benavent
Additional contact information
Nicos Christofides: Imperial College, London, England
Enrique Benavent: Universidad de Valencia, Valencia, Spain

Operations Research, 1989, vol. 37, issue 5, 760-768

Abstract: 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, we 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 us 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.

Keywords: facilities/equipment planning: quadratic assignment problem; special case; networks/graphs; tree algorithms: dynamic programming algorithm; programming; integer: bounds by Lagrangian relaxation (search for similar items in EconPapers)
Date: 1989
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.37.5.760 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:37:y:1989:i:5:p:760-768

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().