A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method

A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method

0.00 Avg rating0 Votes
Article ID: iaor19993114
Country: Netherlands
Volume: 108
Issue: 3
Start Page Number: 629
End Page Number: 640
Publication Date: Aug 1998
Journal: European Journal of Operational Research
Authors: , ,
Keywords: programming: branch and bound, programming: integer, programming: mathematical
Abstract:

This paper presents a new branch-and-bound algorithm for solving the quadratic assignment problem (QAP). The algorithm is based on a dual procedure (DP) similar to the Hungarian method for solving the linear assignment problem. Our DP solves the QAP in certain cases, i.e., for some small problems (N<7) and for numerous larger problems (7<N<16) that arise as sub-problems of a larger QAP such as the Nugent 20. The DP, however, does not guarantee a solution. It is used in our algorithm to calculate lower bounds on solutions to the QAP. As a result of a number of recently developed improvements, the DP produces lower bounds that are as tight as any which might be useful in a branch-and-bound algorithm. These are produced relatively cheaply, especially on larger problems. Experimental results show that the computational complexity of our algorithm is lower than known methods, and that its actual runtime is significantly shorter than the best known algorithms for QAPLIB test instances of size 16 through 22. Our method has the potential for being improved and therefore can be expected to aid in solving even larger problems.

Reviews

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