A Constructive Method for Improving Lower Bounds for a Class of Quadratic Assignment Problems
Jaishankar Chakrapani, Jadranka Skorin-Kapov
Operations Research · 1994 · Volume 42 · Issue 5
Abstract
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.
Keywords
facilities/equipment planning, location: quadratic assignment program, programming: heuristic combinatorial optimization, lower bounds
Enable JavaScript for citation tools and additional paper interactions.