 |
Génération de matrices pour la programmation quadratique binaire
1 : Laboratoire d'Informatique de Paris-Nord
(LIPN)
Université Paris XIII - Paris Nord, CNRS : UMR7030, Institut Galilée
Institut Galilée 99, avenue J.B Clément 93430 VILLETANEUSE -
France
Nous proposons dans ce travail une nouvelle approche pour la génération de bornes de très bonne qualité pour la programmation quadratique binaire (objectif et contraintes quadratiques).
Nous présentons une nouvelle relaxation basée sur le Boolean Quadric Polytope que nous résolvons via une reformulation de Dantzig-Wolfe dans l'espace des matrices.
