A LAGRANGIAN-RELAXATION ALGORITHM FOR SPARSE QUADRATIC ASSIGNMENT PROBLEMS

The Task Assignment Problem (TAP) arises in distributed computing environments and is a relaxed version of the Quadratic Assignment Problem (QAP). In this paper we present a new approach to the QAP which relies on the relationship between the two problems. First, by using the TAP, Lagrangian relaxation lower bounds are obtained for QAPs whose underlying flow graph is a k-tree, a generalization of ordinary trees. Second, for QAPs on arbitrary flow graphs the TAP solution is combined with the well-known Gilmore-Lawler procedure to get an improved bound. Methods to speed-up the branch and bound search are presented, based on the sequence in which the machines are examined and on the use of the linear assignment problem. Finally, we report on our computational results.