COMPUTING LOWER BOUNDS FOR THE QUADRATIC ASSIGNMENT PROBLEM WITH AN INTERIOR-POINT ALGORITHM FOR LINEAR-PROGRAMMING

An example of the quadratic assignment problem (QAP) is the facility l ocation problem, in which n facilities are assigned, at minimum cost, to n sites. Between each pair of facilities, there is a given amount o f flow, contributing a cost equal to the product of the flow and the d istance between sites to which the facilities are assigned. Proving op timality of QAPs has been limited to instances having fewer than 20 fa cilities, largely because known lower bounds are weak. We compute lowe r bounds for a wide range of QAPs using a linear programming-based low er 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 line ar programs, which can be large even for small QAPs, are solved with a n interior point code that uses a preconditioned conjugate gradient al gorithm to compute the interior point directions. Attempts to solve th ese 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.