Reformulation quadratique convexe du problème d'affectation quadratique

Session : SS12 / SS12 : Programmation non-linéaire en variables mixtes entières
Jeudi 11 février 15:00 - 16:40 Salle : CI2-07
Sourour Elloumi et Amélie Lambert

Le problème d'affectation quadratique (QAP) est connu dans la littérature depuis les années 50 où il a permis de modéliser un problème de localisation de $n$ équipements sur $n$ sites qui tient compte à la fois du coût d'affectation d'un équipement et de son interaction avec les autres équipements. Aujourd'hui, QAP est considéré comme un problème classique d'Optimisation Combinatoire par le nombre d'études et de publications auxquelles il a donné lieu. Il est également connu comme un modèle générique de plusieurs autres applications. Le but de ce travail est de montrer les résultats de la reformulation quadratique convexe appliquée à QAP. Nous illustrons sur les instances QAPLIB, largement utilisées pour mesurer l'efficacité des différentes méthodes.

Mots clés : Programmation quadratique en variables binaires Affectation quadratique, Linéarisation, Reformulation quadratique convexe