SEMIDEFINITE PROGRAMMING RELAXATIONS FOR THE QUADRATIC ASSIGNMENT PROBLEM

Semidefinite programming (SDP) relaxations for the quadratic assignmen t problem (QAP) are derived using the dual of the (homogenized) Lagran gian dual of appropriate equivalent representations of QAP. These rela xations result in the interesting, special, case where only the dual p roblem of the SDP relaxation has strict interior, i.e., the Slater con straint qualification always fails for the primal problem. Although th ere is no duality gap in theory, this indicates that the relaxation ca nnot be solved in a numerically stable way. By exploring the geometric al structure of the relaxation, we are able to find projected SDP rela xations. These new relaxations, and their duals, satisfy the Slater co nstraint qualification, and so can be solved numerically using primal- dual interior-point methods. For one of our models, a preconditioned c onjugate gradient method is used for solving the large linear systems which arise when finding the Newton direction. The preconditioner is f ound by exploiting the special structure of the relaxation. See e.g., Vandenverghe and Boyd (1995) for a similar approach for solving SDP pr oblems arising from control applications. Numerical results are presen ted which indicate that the described methods yield at least competiti ve lower bounds.