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.
