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 bull have been given by Padberg and Rijal (1996). 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.
quadratic assignment linearization facets cutting plane algorithm