A Constructive Method for Improving Lower Bounds for a Class of Quadratic Assignment Problems

Jaishankar Chakrapani and Jadranka Skorin-Kapov
Additional contact information
Jaishankar Chakrapani: Environmental Systems Research Institute, Redlands, California
Jadranka Skorin-Kapov: State University of New York at Stony Brook, Stony Brook, New York

Operations Research, 1994, vol. 42, issue 5, 837-845

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 (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.5.837 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:42:y:1994:i:5:p:837-845

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().