Semidefinite Programming Relaxations for the Quadratic Assignment Problem

Qing Zhao, Stefan E. Karisch, Franz Rendl and Henry Wolkowicz
Additional contact information
Qing Zhao: University of Waterloo
Stefan E. Karisch: University of Copenhagen
Franz Rendl: Graz University of Technology
Henry Wolkowicz: University of Waterloo

Journal of Combinatorial Optimization, 1998, vol. 2, issue 1, No 5, 109 pages

Abstract: 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 (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (40)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009795911987 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:2:y:1998:i:1:d:10.1023_a:1009795911987

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009795911987

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().