Co-k-plexes et coloration k-defective : polyèdres et algorithmes

Co-k-plexes and k-defective coloring : polytopes and algorithms Cette thèse propose plusieurs résultats sur les co-k-plexes, qui sont des ensembles de sommets induisant un graphe avec un degré maximum k-1. La première partie de la thèse explore plusieurs caractérisations d'une nouvelle sous-classe de graphes parfaits, appelés graphes contraction parfaits. Ce sont l'ensemble des graphes parfaits restant parfaits après contraction de n'importe quel ensemble d'arêtes. Cette classe de graphes est caractérisée de quatre manières différentes. Parmi ces résultats, un graphe est contraction parfait si et seulement s'il est parfait et que la contraction de n'importe quelle arête préserve sa perfection. Cela permet une caractérisation des graphes contraction parfait en termes de sous-graphes induits interdits, ainsi qu'un algorithme polynomial pour leur reconnaissance. Le utter graphe u(G) d'un graphe G est un graphe dont les stables sont en bijection avec les co-2-plexes de G. Il est démontré que u(G) est parfait si et seulement si G est contraction parfait. Puisque le problème de stable de poids maximum est solvable en temps polynomial sur les graphes parfaits, il en va de même pour le problème de co-2-plex de poids max sur les graphes contraction parfait. Une formulation étendue pour le polytope co-2-plex des graphes contraction parfait est obtenue en considérant le polytope de l'ensemble des stable de son utter graphe. Notez que cette formulation devient compacte pour les graphes chordaux. De plus, avec des contraintes d'intégrité, cette formulation devient une formulation ILP valide pour n'importe quel graphe G, conduisant à une comparaison entre cette formulation ILP étendue et la formulation classique de la littérature. D'un point de vue théorique, cette nouvelle formulation a une relaxation linéaire de meilleure qualité, et d'un point de vue expérimental, plusieurs implémentations de cette nouvelle formulation sont proposées et se révèlent compétitives. La deuxième partie de la thèse concerne le problème k-defective coloring qui consiste à recouvrir les sommets d'un graphe avec un nombre minimum de co-k-plexes. Ce problème est formulé comme une formulation set covering contenant une variable par co-k-plex, et résolu en utilisant une méthode de branch and price. Un algorithme de branch and price pour le k-defective coloring proposé par Furini et al. est d'abord décrit et mis en œuvre en utilisant le framework SCIP, et plusieurs améliorations sont proposées pour les cas k=1,2. Cette thèse propose plusieurs alternances entre les phases de cutting et de pricing et en particulier deux stratégies paramétrées sont conçues pour se débarrasser du tailing off effect. La génération de colonnes peut aussi être stabilisée en utilisant des inégalités optimales duales. Cette technique consiste à ajouter au RMP un ensemble de colonnes supplémentaires correspondant à des inégalités ne coupant aucun point optimal du problème dual. Cette méthode est expérimentalement efficace pour stabiliser la génération de colonnes à chaque nœud de l'arbre de branchement. Différentes façons de combiner les inégalités de renforcement et les inégalités optimales duales sont étudiées. Pour k=2, le problème de pricing se réduit à calculer un problème de co-2-plex pondéré maximum. Par conséquent, une variante de la méthode de branch and price dans laquelle le pricing est résolu en utilisant la formulation ILP de la première partie de la thèse est évaluée expérimentalement. De nouvelles inégalités duales sont proposées pour la stabilisation du cas k=2. Contrairement à ce qui existe dans la littérature, les inégalités duales proposées peuvent couper chaque solution optimale du dual. Cependant, chaque solution primale entière avec des valeurs positives dans les colonnes supplémentaires peut être transformée en une solution entière du problème d'origine avec la même valeur optimale. Une amélioration expérimentale significative est observée pour le problème de 2-defective coloring.