##
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.

Contact: hwolkowi@orion.math.uwaterloo.ca

(Bibliographic info)