Réduction de l’espace de recherche du Problème de la Somme Coloration Minimum d’un graphe

Le Problème de la Somme Coloration Minimum (MSCP) d’un graphe est un problème d’optimisation combinatoire dont l’objectif est de déterminer une coloration valide minimisant la somme des poids associés aux couleurs utilisées. Le nombre minimum de couleurs dans une solution optimale de MSCP est appelé la force du graphe, et la somme des poids des couleurs utilisées est appelée la somme chromatique du graphe. L’objectif de cette thèse a été d’étudier MSCP afin de proposer de nouvelles approches permettant sa résolution. La contribution de cette thèse est double. Premièrement, nous avons introduit deux nouvelles bornes supérieures de la force d’un graphe et une nouvelle borne inférieure de la somme chromatique, basées sur la notion de motif que nous avons adapté de la littérature. L’intérêt majeur de ces travaux est la réduction de l’espace des solutions de MSCP. Deuxièmement, nous avons proposé plusieurs approches de résolution exacte de MSCP. La première méthode consiste en une modélisation de MSCP en un formalisme MaxSAT partiel pondéré ou MinSAT partiel pondéré afin d'utiliser les solveurs MaxSAT/MinSAT de l'état de l'art pour résoudre MSCP. Nous avons montré que notre borne de la force du graphe permet de réduire grandement la taille des instances MaxSAT/MinSAT obtenues et de rendre les solveurs MaxSAT compétitifs pour résoudre MSCP. Les deux autres méthodes de résolution proposées sont des approches de type Branch-and-Bound appelées BBMSCP et 3LMSCP. La différence entre BBMSCP et 3LMSCP est que 3LMSCP exploite la partition du graphe en stables afin de ne pas considérer les colorations symétriques.