Lower Bounds for the Quadratic Assignment Problem Based upon a Dual Formulation

Peter Hahn and Thomas Grant
Additional contact information
Peter Hahn: Sci-Tech Services, Inc., Philadelphia, Pennsylvania and University of Pennsylvania, Philadelphia, Pennsylvania
Thomas Grant: Bear Stearns and Co., New York, New York

Operations Research, 1998, vol. 46, issue 6, 912-922

Abstract: A new bounding procedure for the Quadratic Assignment Problem (QAP) is described which extends the Hungarian method for the Linear Assignment Problem (LAP) to QAPs, operating on the four dimensional cost array of the QAP objective function. The QAP is iteratively transformed in a series of equivalent QAPs leading to an increasing sequence of lower bounds for the original problem. To this end, two classes of operations which transform the four dimensional cost array are defined. These have the property that the values of the transformed objective function Z′ are the corresponding values of the “old” objective function Z, shifted by some amount C. In the case that all entries of the transformed cost array are nonnegative, then C is a lower bound for the initial QAP. If, moreover, there exists a feasible solution U to the QAP, such that its value in the transformed problem is zero, then C is the optimal value of Z and U is an optimal solution for the original QAP. The transformations are iteratively applied until no significant increase in constant C as above is found, resulting in the so called Dual Procedure (DP).Several strategies are listed for appropriately determining C, or equivalently, transforming the cost array. The goal is the modification of the elements in the cost array to obtain new equivalent problems that bring the QAP closer to solution. In some cases the QAP is actually solved, though solution is not guaranteed. The close relationship between the DP and the Linear Programming formulation of Adams and Johnson is presented. The DP attempts to solve Adams and Johnson's CLP, a continuous relaxation of a linearization of the QAP. This explains why the DP produces bounds close to the optimum values for CLP calculated by Johnson in her dissertation and by Resende, et al. in their Interior Point Algorithm for Linear Programming.The benefit of using DP within a branch-and-bound algorithm is described. Then, two versions of DP are tested on the Nugent test instances from size 5 to size 30, as well as several other test instances from QAPLIB. These compare favorably with earlier bounding methods.

Keywords: Integer programming; bounding method for Quadratic Assignment Problem (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.6.912 (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:46:y:1998:i:6:p:912-922

Access Statistics for this article

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