Computing Lower Bounds for the Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming

Mauricio G. C. Resende, K. G. Ramakrishnan and Zvi Drezner
Additional contact information
K. G. Ramakrishnan: AT&T Bell Laboratories, Murray Hill, New Jersey
Zvi Drezner: California State University, Fullerton, California

Operations Research, 1995, vol. 43, issue 5, 781-791

Abstract: An example of the quadratic assignment problem (QAP) is the facility location problem, in which n facilities are assigned, at minimum cost, to n sites. Between each pair of facilities, there is a given amount of flow, contributing a cost equal to the product of the flow and the distance between sites to which the facilities are assigned. Proving optimality of QAPs has been limited to instances having fewer than 20 facilities, largely because known lower bounds are weak. We compute lower bounds for a wide range of QAPs using a linear programming-based lower bound studied by Z. Drezner (1995). On the majority of QAPs tested, a new best known lower bound is computed. On 87% of the instances, we produced the best known lower bound. On several instances, including some having more the 20 facilities, the lower bound is tight. The linear programs, which can be large even for small QAPs, are solved with an interior point code that uses a preconditioned conjugate gradient algorithm to compute the interior point directions. Attempts to solve these instances using the CPLEX primal simplex algorithm as well as the CPLEX barrier (primal-dual interior point) method were successful only for the smallest instances.

Keywords: facilities/equipment planning: quadratic assignment; programming; linear; algorithms; large-scale systems: interior point method; programming; quadratic: interior point method (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.43.5.781 (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:43:y:1995:i:5:p:781-791

Access Statistics for this article

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