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: | Hahn Peter, Grant Thomas, Hall Nat |
Keywords: | programming: branch and bound, programming: integer, programming: mathematical |
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 (