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 -