Soutenances de thèse

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 la 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 ensembles 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 du plus grand ensemble stable est solvable en temps polynomial sur les graphes parfaits, il en va de même pour le problème du plus grand co 2-plex pondéré pour 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 cordaux. De plus, avec des contraintes d’intégrité supplémentaires, cette formulation devient une formulation ILP valide pour 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. Pour k=1, des inégalité de rang un de Chvátal-Gomory sont d’abord ajoutées de manière dynamique lors de la résolution de la relaxation linéaire à chaque n?ud de l’arbre de branchement. L’ajout de contraintes dans un cadre de génération de colonnes est généralement réalisé lorsque le critère de convergence de la génération de colonnes est atteint, ce qui donne la priorité à la génération de nouvelles colonnes plutôt qu’à de nouvelles lignes. D’autre part, la génération de colonnes est connue pour souffrir du tailing off effect qui consiste en une séquence d’ajout de variables non améliorantes. Pour résoudre ce problème, des alternances entre les phases de cutting et de pricing sont étudiées et en particulier deux stratégies paramétrées sont conçues pour se débarrasser de l’effet d’affaiblissement. La génération de colonnes peut ê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 RMP dual. Cette méthode est expérimentalement efficace pour stabiliser la génération de colonnes à chaque noeud 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.