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

Abstract

In this paper we consider all the known exponential-sized families of facet-defining inequalities of the QAP-polytope. We describe a new family of valid inequalities that we show to be facet-defining.

We also show that membership testing (and hence optimizing) over some of the known classes of inequalities is coNP-complete.

Keywords

• Facet-Defining Inequalities
• QAP-Polytope