On the Complexity of Some Facet-Defining Inequalities of the QAP-Polytope

The Quadratic Assignment Problem (QAP) is a well-known NP-hard problem that is equivalent to optimizing a linear objective function over the QAP polytope. The QAP polytope with parameter n – \(\mathrm {QAP}_{n}\) – is defined as the convex hull of rank-1 matrices \(xx^T\) with x as the vectorized \(n\times n\) permutation matrices.