Semidefinite Programming Relaxations for the Quadratic Assignment Problem |
| |
Authors: | Qing Zhao Stefan E. Karisch Franz Rendl Henry Wolkowicz |
| |
Affiliation: | (1) Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, N2L, 3G1, Canada;(2) Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen, Denmark;(3) Department of Mathematics, Graz University of Technology, Steyrergasse 30, A-8010 Graz, Austria;(4) Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, N2L, 3G1, Canada |
| |
Abstract: | 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.For one of our models, 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. See e.g., Vandenverghe and Boyd (1995) for a similar approach for solving SDP problems arising from control applications.Numerical results are presented which indicate that the described methods yield at least competitive lower bounds. |
| |
Keywords: | quadratic assignment problem semidefinite programming relaxations interior-point methods large scale problems |
本文献已被 SpringerLink 等数据库收录! |
|