A new relaxation framework for quadratic assignment problems based on matrix splitting

  • Quadratic assignment problems (QAPs) are known to be among the hardest discrete optimization problems. Recent study shows that even obtaining a strong lower bound for QAPs is a computational challenge. In this paper, we first discuss how to construct new simple convex relaxations of QAPs based on various matrix splitting schemes. Then we introduce the so-called symmetric mappings that can be used to derive strong cuts for the proposed relaxation model. We show that the bounds based on the new models are comparable to some strong bounds in the literature. Promising experimental results based on the new relaxations are reported.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Jiming Peng, Hans Mittelmann, Xiaoxue Li
DOI:https://doi.org/10.1007/s12532-010-0012-6
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2010
Tag:Software; Theoretical Computer Science
Volume:2
Issue:1
Page Number:19
First Page:59
Last Page:77
Mathematical Programming Computation :MPC 2010 - Issue 1
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.