An exact algorithm for the Quadratic Assignment Problem on a tree

An exact algorithm for the Quadratic Assignment Problem on a tree

0.00 Avg rating0 Votes
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: ,
Keywords: networks
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, 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.

Reviews

Required fields are marked *. Your email address will not be published.