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 F_opt and F_res are constructed such that F = F_opt + F_res, and the optimal solution to QAP(D, F_opt) is known. Any existing lower bound can then be applied to QAP(D, F_res), which in sum with the optimal value for QAP(D, F_opt), 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.