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

Pawan Aurora, Hans Raj Tiwary

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 par…