Calcul de décompositions arborescentes

Calcul de décompositions arborescente

Défauts des décompositions existantes

Les décompositions existantes, dont M in-F ill constitue l’heuristique de l’état de l’art pour la communauté CP et au-delà, visent notamment à minimiser la taille des clusters de la décomposition et ainsi la largeur w + de celles-ci. M in-F ill est surtout connue pour sa bonne approximation de la largeur arborescente w et par son temps de calcul qui reste raisonnable par rapport aux méthodes exactes de calcul de décompositions. Pour rappel, la décomposition issue de M in-F ill est calculée en deux étapes : • La première étape consiste à trianguler le graphe G, c’est-à-dire à rajouter les arêtes nécessaires dans le but d’établir un ordre d’élimination parfait σ et d’obtenir un graphe triangulé G′ σ à partir de G. Pour construire l’ordre d’élimination parfait σ, M in-F ill ordonne les sommets de G de 1 à n en choisissant comme sommet suivant le sommet qui nécessite d’ajouter un minimum d’arêtes pour compléter son voisinage ultérieur. Généralement, M in-F ill casse les égalités d’une façon arbitraire. Après avoir rajouté les arêtes en question, M in-F ill continue à procéder de la même façon jusqu’à ce que tous les sommets de G soient numérotés. Cet algorithme est une instanciation spécifique de l’algorithme Heuristique-H de la partie 1.3.2.3. Il est montré par l’algorithme 3.1. • La deuxième étape consiste, une fois le graphe G triangulé, à identifier les cliques maximales de G′ σ , grâce à σ, qui formeront chacune un cluster de la décomposition. En ajoutant a priori moins d’arêtes, nous pouvons espérer produire des cliques maximales plus petites et par voie de conséquence une décomposition de largeur plus proche de l’optimum. Cependant, M in-F ill, comme toutes les méthodes de calcul de décompositions basées sur la triangulation, présente plusieurs inconvénients liés d’une part à la façon dont elle procède pour calculer une décomposition et d’autre part à l’intérêt de l’utilisation de cette dernière vis-à-vis de la résolution. Nous utilisons, par la suite, la notation G′ au lieu de G′ σ lorsqu’il n’y a pas d’ambigu¨ıté. 

Effet boule de neige 

Nous rappelons tout d’abord que la triangulation obtenue par les heuristiques de triangulation n’est généralement pas minimum, ni même minimale [Kjaerulff, 1990]. Autrement dit, il est possible de pouvoir supprimer des arêtes ajoutées à G′ tout en gardant un graphe G′ triangulé. L’ajout des arêtes additionnelles non nécessaires vis-à-vis de la triangulation entraîne forcément un surcoˆut au niveau du temps de triangulation en pratique. Plus important, cela peut entraîner une augmentation de la taille des clusters de la décomposition et de sa largeur w +. En outre, ces heuristiques présentent un phénomène qui peut être qualifié de l’effet boule de neige. Il est caractérisé par un ajout considérable d’arêtes au graphe triangulé (potentiellement en O(n ′3 ) pour une grille ou grid graph de n ′ × n ′ sommets, par exemple). Informellement, l’effet boule de neige consiste en une augmentation du nombre d’arêtes ajoutées au graphe entraînant à leur tour l’ajout d’un plus grand nombre d’arêtes. Souvent, cet aspect est dˆu à un ajout d’arêtes ne respectant pas ce qui serait souhaitable au regard de la topologie du graphe. En effet, la démarche suivie par ces heuristiques ignore la topologie du graphe. Par exemple, M in-F ill ne tient compte que du nombre d’arêtes nécessaires pour compléter le voisinage ultérieur d’un sommet. Au niveau de la topologie du graphe, nous nous intéressons notamment à l’indépendance entre des sous-graphes du graphe G, c’est-à-dire à l’absence d’arêtes entre deux sous-graphes de G. La plupart des heuristiques de triangulation ne prennent pas en compte, du moins explicitement, ce paramètre pendant la triangulation et peuvent potentiellement ajouter des arêtes entre deux sous-graphes indépendants, ce qui serait inutile du point de vue de la triangulation. Ainsi, la survenue de l’effet boule de neige est tout à fait possible avec ces heuristiques. Nous illustrons ce phénomène par la figure 3.1 en utilisant M in-F ill. Toutefois, nous pouvons trouver des exemples similaires pour les autres heuristiques comme MCS [Tarjan and Yannakakis, 1984], Lex [Rose et al., 1976], M inimum-Degree[M arkowitz, 1957] . . .

Efficacité des décompositions vis-à-vis de la résolution

Grâce aux heuristiques de calcul de décompositions, les décompositions arborescentes ont déjà été exploitées avec succès pour résoudre des instances (W)CSP et pour le comptage [Jégou and Terrioux, 2003, 2004b; Givry et al., 2006; Favier et al., 2009; Sanchez et al., 2009; Allouche et al., 2015]. Cependant, les décompositions existantes ne sont pas nécessairement les plus adaptées du point de vue de la résolution [Jégou et al., 2005; Jégou and Terrioux, 2014b]. D’ailleurs, le temps de calcul de décomposition peut effectivement largement dépasser le temps de résolution des méthodes non basées sur une décomposition dans certains cas. En plus, même si la largeur w + des décompositions calculées demeure très intéressante par rapport à la largeur optimale w, il ne semble pas que ce critère soit le plus pertinent au regard de l’efficacité de la résolution. En effet, les décompositions existantes, qu’elles soient ou non basées sur la triangulation, présentent les problèmes listés ci-dessous. Limitation de la liberté de l’heuristique de choix de variables Afin de garantir une complexité en temps en O(exp(w +)), les méthodes structurelles efficaces comme BT D utilisent un ordre d’affectation des variables qui est partiellement induit par la décomposition considérée. Quand des heuristiques comme M in-F ill sont utilisées, cette liberté est même encore plus restreinte du fait du nombre limité de sommets propres dans les clusters. Le nombre de sommets propres peut d’ailleurs atteindre un seul sommet pour certains clusters. Dans ce cas, la liberté du choix de la prochaine variable se limite au choix du prochain cluster fils. Si, en plus, un cluster n’a qu’un seul cluster fils, cela implique une résolution exploitant un ordre de choix de variables total, donc statique. Or, il est bien connu que pour avoir une résolution efficace, il est souhaitable d’avoir une liberté maximale pour le choix des prochaines variables à affecter et le plus de dynamicité possible à ce niveau. Non-connexité des clusters La décomposition calculée peut éventuellement contenir des clusters non connexes (c’est-à-dire des clusters Ei tels que G[Ei ] possède plusieurs composantes connexes), ce qui peut conduire à une forte dégradation de l’efficacité de la résolution [Jégou and Terrioux, 2014b]. Les figures 3.3, 3.4 et 3.5 montrent trois décompositions formées de 4 clusters, Ei ayant comme père le cluster Ep(i) et un fils noté Ej . Le cluster Ek est à son tour le fils de Ej . Nous nous focalisons sur le cluster Ei et nous distinguons trois cas possibles : • Cas de la figure 3.3 : Ei est non connexe et le graphe G[Ei\(Ei ∩ Ep(i) )] contient deux composantes connexes indépendantes. Tout d’abord, la présence de plusieurs composantes connexes dans un cluster Ei peut diminuer l’efficacité de la résolution localement. En effet, si l’une des composantes connexes est insatisfaisable et que ce n’est pas le cas des autres composantes connexes, la recherche peut potentiellement explorer toutes les solutions des autres composantes connexes avant de prouver l’insatisfaisabilité de celle-ci. Dans le cadre du problème CSP ou #CSP, en utilisant BT D, les variables de Ei distribuées dans plusieurs composantes connexes doivent être assignées d’une façon cohérente. Si le sous-problème enraciné en Ei (contenan les variables de Ei , Ej et Ek) est facile, c’est-à-dire possède beaucoup de solutions, l’affectation du cluster Ei est a priori rapide et s’étend plus probablement à une solution du sous-problème en question. Dans ce cas, la non-connexité du cluster Ei ne pose pas un véritable problème. Si au contraire le sous-problème n’admet que très peu de solutions, voire aucune, la résolution assigne les variables de Ei plus difficilement en passant potentiellement d’une composante connexe à l’autre. En effet, si des techniques de filtrage sont utilisées, l’affectation d’une variable xi d’une composante connexe n’a que très peu d’influence sur les domaines des variables des autres composantes connexes. Donc, ces variables seront assignées sans vraiment tenir compte de l’affectation de xi . C’est ainsi qu’une incohérence pourrait être détectée plus tard dans la recherche lors du traitement de l’un des fils de Ei . Cela diminue l’efficacité de la résolution en gaspillant du temps, mais aussi, en consommant de l’espace, en augmentant essentiellement le nombre de nogoods enregistrés. De même, dans le cadre du problème WCSP, la non-connexité peut avoir un impact sur la qualité de l’affectation de Ei (en termes de coˆut) et peut ainsi demander plusieurs retours à Ei avant de pouvoir trouver la solution optimale. • Cas de la figure 3.4 : Le fait que le cluster Ei soit non connexe et que G[Ei\(Ei∩Ep(i) )] soit connexe signifie que le cluster Ei est non connexe à cause de la non-connexité du séparateur. Vu que les variables du séparateur sont assignées avant l’affectation des variables propres de Ei , la non-connexité n’induit alors aucun problème dans ce cas au niveau de la résolution. • Cas de la figure 3.5 : Le fait que le cluster Ei soit connexe et que G[Ei\(Ei ∩ Ep(i) )] ne le soit pas nous refait revenir au cas de la figure 3.3. En effet, comme les variables du séparateur sont instanciées avant celles des variables propres de Ei cela produit un cluster Ei non connexe lors de l’instanciation de ses variables propres. En guise de conclusion, un cluster Ei doit avoir le sous-graphe G[Ei\(Ei ∩Ep(i) )] connexe. Notons que le choix du cluster racine indique l’orientation de la décomposition et ainsi les liens de parenté et filiation qui existent entre les clusters. Donc, la présence non souhaitable des cas des figures 3.3 et 3.5 dépend du choix de ce cluster. Or, il n’y a pas de garantie de pouvoir trouver un cluster racine convenable, c’est-à-dire qui garantit l’absence des cas des figures 3.3 et 3.5.