A constructive method for improving lower bounds for a class of quadratic assignment problems.

A new approach to evaluate lower bounds for a class of quadratic assignment problems (QAP) is presented. An instance of a QAP of size n is specified by two n × n matrices D and F, and is denoted by QAP(D, F). This approach is presented for QAPs where D is the matrix of rectilinear distances between points on a regular grid. However, it can easily be generalized to a wider class of problems. Two matrices Fopt and Fres are constructed such that F = Fopt + Fres, and the optimal solution to QAP(D, Fopt) is known. Any existing lower bound can then be applied to QAP(D, Fres), which in sum with the optimal value for QAP(D, Fopt), provides a lower bound to QAP(D, F). Thus, this method could serve as a reduction process to possibly improve the results from a variety of bounding techniques. This approach is tested on two bounds from the literature, the Gilmore-Lawler bound (GLB) and an eigenvalue bound (PB), for various problems of size ranging from 6-49. Computational results show a good improvement in bounds for all the test problems. An extension of our method to a more general class of QAPs is also presented. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research is the property of INFORMS: Institute for Operations Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)