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
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
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
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
Lagrangian relaxation when obtaining the SDP relaxation.
Numerical results are presented which indicate
that the described methods yield at least competitive lower bounds.