Bounds for the quadratic assignment problem using the bundle method

• 成果类型: Article
• 署名作者: Rendl, Franz; Sotirov, Renata
• 署名单位: University of Klagenfurt; University of Melbourne
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0038-8
• 发表日期: 2007
• 页码: 505-524
• 关键词: relaxations; CONVERGENCE

摘要

Semidefinite programming (SDP) has recently turned out to be a very powerful tool for approximating some NP-hard problems. The nature of the quadratic assignment problem (QAP) suggests SDP as a way to derive tractable relaxations. We recall some SDP relaxations of QAP and solve them approximately using a dynamic version of the bundle method. The computational results demonstrate the efficiency of the approach. Our bounds are currently among the strongest ones available for QAP. We investigate their potential for branch and bound settings by looking also at the bounds in the first levels of the branching tree.