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 and an eigenvalue bound, 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.
