A new matrix splitting based relaxation for the quadratic assignment problem

Publikationstyp
Conference Paper
Date Issued
2016
Sprache
English
Author(s)
Lange, Marko  
Institut
Zuverlässiges Rechnen E-19  
TORE-URI
http://hdl.handle.net/11420/6287
First published in
Lecture notes in computer science  
Number in series
9582 LNCS
Start Page
535
End Page
549
Citation
Lecture Notes in Computer Science (9582): 535-549 (2016)
Publisher DOI
10.1007/978-3-319-32859-1_45
Scopus ID
2-s2.0-84964005644
Publisher
Springer
Nowadays, the quadratic assignment problem (QAP) is widely considered as one of the hardest of the NP-hard problems. One of the main reasons for this consideration can be found in the enormous difficulty of computing good quality bounds for branch-and-bound algorithms. The practice shows that even with the power of modern computers QAPs of size n>30 are typically recognized as huge computational problems. In this work, we are concerned with the design of a new low-dimensional semidefinite programming relaxation for the computation of lower bounds of the QAP. We discuss ways to improve the bounding program upon its semidefinite relaxation base and give numerical examples to demonstrate its applicability.
Subjects
Quadratic assignment problem
Relaxation
Semidefinite programming
DDC Class
004: Informatik