TY - GEN
T1 - A new matrix splitting based relaxation for the quadratic assignment problem
AU - Lange, Marko
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
KW - Quadratic assignment problem
KW - Relaxation
KW - Semidefinite programming
UR - http://www.scopus.com/inward/record.url?scp=84964005644&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84964005644&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-32859-1_45
DO - 10.1007/978-3-319-32859-1_45
M3 - Conference contribution
AN - SCOPUS:84964005644
SN - 9783319328584
VL - 9582
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 535
EP - 549
BT - Mathematical Aspects of Computer and Information Sciences - 6th International Conference, MACIS 2015, Revised Selected Papers
PB - Springer Verlag
T2 - 6th International Conference on Mathematical Aspects of Computer and Information Sciences, MACIS 2015
Y2 - 11 November 2015 through 13 November 2015
ER -