Paper Info
Title
Computing Lower Bounds for the Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming
Abstract
Abstract A typical example of the quadratic assignment problem (QAP) is the facility location problem, in which a set of n facilities are to be assigned, at minimum cost, to an equal number of locations. 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 locations to which the facilities are assigned. Proving optimality of solutions to quadratic assignment problems has been limited to instances of small dimension (n less than or equal to 20), in part because known lower bounds for the QAP are of poor quality. In this paper, we compute lower bounds for a wide range of quadratic assignment problems using a linear programming-based lower bound,studied by Drezner (1994). On the majority of quadratic assignment problems tested, the computed lower bound is the new best known lower bound. In 87 percent of the instances, we produced the best known lower bound. On several instances, including some of dimension n equal to 20, the lower bound is tight. The linear programs, which can be large even for moderate values of n, are solved with an interior point code that uses a preconditioned conjugate gradient algorithm to compute,the directions taken at each iteration by the interior point algorithm. 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. The quadratic assignment problem (QAP) can be stated as
Year
DOI
Venue
1995
10.1287/opre.43.5.781
Operations Research
Field
DocType
Volume
Conjugate gradient method,Mathematical optimization,Simplex algorithm,Upper and lower bounds,Quadratic assignment problem,Algorithm,Facility location problem,Linear programming,Interior point method,Mathematics
Journal
43
Issue
ISSN
Citations 
5
0030-364X
34
PageRank 
References 
Authors
5.14
14
3
Name
Order
Citations
PageRank
Mauricio G. C. Resende13729336.98
K. G. Ramakrishnan258798.53
Zvi Drezner31195140.69