Semidefinite Programming Relaxations for the Quadratic Assignment Problem

Stefan E. Karisch, Franz Rendl, Henry Wolkowicz, and Qing Zhao

Semidefinite programming (SDP) relaxations for the quadratic assignment problem (QAP) are derived using the dual of the (homogenized) Lagrangian dual of appropriate equivalent representations of QAP. These relaxations result in the interesting, special, case where only the dual problem of the SDP relaxation has strict interior, i.e.\ the Slater constraint qualification always fails for the primal problem. Although there is no duality gap in theory, this indicates that the relaxation cannot be solved in a numerically stable way. By exploring the geometrical structure of the relaxation, we are able to find projected SDP relaxations. These new relaxations, and their duals, satisfy the Slater constraint qualification, and so can be solved numerically using primal-dual interior-point methods. In particular, the special structure gives rise to several interesting inear operators, e.g.: block diagonal; arrow; and the gangster operators. A study of these operators leads to efficient exploitation of sparsity.

A preconditioned conjugate gradient method is used for solving the large linear systems which arise when finding the Newton direction. The preconditioner is found by exploiting the special structure of the relaxation and the above mentioned linear operators.

Feasible solutions for QAP are recovered from the Lagrangian relaxation information; thus illustrating the importance of going through the Lagrangian relaxation when obtaining the SDP relaxation. Numerical results are presented which indicate that the described methods yield at least competitive lower bounds.


(Bibliographic info)