A cutting algorithm for the quadratic assignment problem

We address the Quadratic Assignment Problem following a polyhedral method. We consider the Quadratic Assignment Polytope defined as the convex hull of the solutions of the linearized problem. Its dimension and a minimal description of its affine ball have been given by Padberg and Rijal. Here we propose a large family of valid inequalities inducing facets. We show that the separation problem of this family is NP-complete. We propose a heuristic for the separation problem and a cutting plane algorithm based on this heuristic. Numerical results show the practical interest of this family of inequalities.