1. UN ALGORITHME DE GÉNÉRATION DE COUPES POUR LE PROBLÈME DE L'AFFECTATION QUADRATIQUE.
- Author
-
Blanchard, Aurélien, Elloumi, Sourour, Faye, Alain, and Wicker, Nicolas
- Subjects
QUADRATIC assignment problem ,COMBINATORIAL optimization ,POLYHEDRA ,MATHEMATICAL inequalities ,NP-complete problems ,COMPUTATIONAL complexity ,ALGORITHMS ,HEURISTIC programming ,ALGEBRA - Abstract
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 hull 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. [ABSTRACT FROM AUTHOR]
- Published
- 2003
- Full Text
- View/download PDF