Calcul des hypertrees décompositions pondérées

Abstract

Les problèmes de satisfaction de contraintes (CSP) permettent de modéliser et de résoudre beaucoup de problèmes du monde réel. Cependant, ils sont connus pour être des problèmes NP complets. Leur complexité théorique est exponentielle en la taille du problème. Cependant, il est bien connu que les CSP ayant une structure acyclique en déterminant des sous classes parmi ces CSP cycliques traitables de manière polynomiale. Les techniques de décompositions structurelles permettent de déterminer des sous classes traitables en temps polynomial. Ces méthodes regroupent des variables ou des contraintes en des clusters de telle sorte que le CSP obtenu ait une structure d’arbre. Parmi ces méthode, la méthode la plus générale est la méthode dite « hypertree decomposition » où la qualité de la décomposition est basé uniquement sur la largeur de la décomposition hors qu’il y a d’autre paramètre qui peuvent guider à une meilleur décomposition, chose qui a permet à introduire une nouvelle méthode appelé « weighted hypertree decomposition ». Cependant, l’algorithme présenté pour le calcul de cette méthode présente une complexité exponentielle. Pour cela, nous proposant un nouvel algorithme « Tabu Search for Weighted Hypertree Décomposition » basé sur une méthode méta heuristique (recherche taboue). Cet algorithme est testé et évalué sur des différents problèmes connus dans la littérature et l’industrie