Abstract (FR)

Nous considérons l'application d'un schéma de décomposition de Dantzig-Wolfe sur un programme linéaire en variables 0-1 dans lequel un sous-ensemble de contraintes definit un polytope de stable. Nous comparons les relaxations linéaires du programme de départ et du programme maître (obtenu en décomposant sur les contraintes de stable) en fonction de différentes représentations du polytope de stable. Dans le cas de graphe parfait (et en particulier de graphe de co-comparabilité), la relaxation linéaire du programme maître peut être résolue en un temps polynomial alors que ce n'est pas le cas dans le cas général. En conséquence, il peut être intéressant de décomposer uniquement sur un sous-ensemble de contraintes de stable (celles définissant un problème de stable sur un graphe parfait) de façon à définir un nouveau programme maître pouvant être résolu en un temps polynomial et, renforçant la relaxation continue du programme de départ.