Similitudes entre les problèmes CSP et #CSP

Similitudes entre les problèmes CSP et #CSP

Trivialement, les deux problèmes CSP pour la décision et #CSP pour le comptage se rapprochent du fait de la nature de la question à laquelle ils répondent. Etant donnée ´ une instance, le problème de décision CSP consiste à dire si cette instance possède une solution. Quant au problème du comptage #CSP, il vise à compter le nombre de solutions de cette instance. Evidemment, si nous ne sommes pas capables de décider si une instan   ce a une solution, nous ne serons pas en mesure de compter son nombre de solutions. De même, si nous pouvons compter efficacement le nombre de solutions d’une instance, nous répondons automatiquement à la question de la cohérence de l’instance. La relation étroite entre ces deux problèmes a permis d’étendre les méthodes de résolution du problème CSP naturellement aux méthodes de comptage. Ainsi, les méthodes énumératives classiques de résolution du problème CSP telles que MAC et RF L ont été étendues et exploitées pour le comptage du nombre de solutions d’une instance. Dans ce cas, elles explorent l’espace de recherche afin d’énumérer l’ensemble des solutions du  problème et ne se contentent pas de la détection d’une seule solution. La façon dont ces méthodes procèdent induit une redondance des sous-espaces de recherche visités. Ces redondances sont encore plus pénalisantes dans le cadre du problème du comptage puisque l’effort effectué pour chaque sous-problème est plus important vu que l’espace de recherche visité serait potentiellement plus grand que dans le cas du problème de décision. De ce fait, ces méthodes ne sont pas efficaces en pratique notamment pour les problèmes ayant un très grand nombre de solutions (sur le benchmark auquel nous allons nous intéresser dans ce chapitre certaines instances possèdent un nombre de solutions de l’ordre de 10250 solutions). Dans ce cas, la capacité de l’énumération est dépassée. Quant aux méthodes structurelles, elles ont été adaptées au problème #CSP. Leur intérêt réside dans leur aptitude à fournir des méthodes exactes de comptage qui ont une complexité théorique en temps beaucoup plus intéressante que celle des méthodes énumératives, exponentielle en n. En pratique, ces méthodes ont également prouvé une amélioration importante en termes d’efficacité. Dans cet esprit, dans [Favier et al., 2009], il a été proposé d’adapter la méthode BT D au problème #CSP aboutissant ainsi à une méthode appelée #BT D. #BT D a recours à l’enregistrement à la façon de BT D ce qui le rend efficace en pratique contrairement aux méthodes classiques. En effet, BT D enregistre pour chaque sous-problème induit par une affectation donnée un (no)good structurel qui indique si cette affectation admet une extension sur ce sous-problème. Quant à #BT D, c’est le nombre d’extensions de cette affectation qui sera enregistré. Si ultérieurement pendant la recherche, cette même affectation est réalisée, #BT D réutilise le nombre de solutions enregistré pour le sous-problème déjà visité et par voie de conséquence évite certaines redondances. Nous nous focalisons dans la partie suivante sur #BT D et nous expliquons comment cet algorithme compte le nombre de solutions des instances CSP grˆace à la décomposition arborescente de leur (hyper)graphe de contraintes.

Adaptation de BTD à #BTD

La méthode #BT D se base sur les mêmes principes que la méthode BT D utilisée pour résoudre le problème CSP. Elle exploite une décomposition calculée préalablement avant le début de la recherche. Dans la suite de ce chapitre, nous nous basons sur l’exemple de la décomposition de la figure 6.1 pour illustrer le comportement de l’algorithme #BT D et plus tard celui de l’algorithme #EBT D. #BT D, à l’instar de BT D, exploite la propriété essentielle de la décomposition arborescente. En effet, le fait d’assigner les variables d’un séparateur entre deux clusters de la décomposition sépare le problème initial en deux problèmes, qui peuvent être résolus indépendamment. Si le séparateur en question sépare deux clusters Ei et Ej de la décomposition (avec Ej le cluster fils de Ei), le premier sous-problème est celui enraciné en Ej . Il contient l’ensemble des variables des clusters de Desc(Ej ) (noté VDesc(Ej ) ) et est noté Pj |A[Ei ∩ Ej ] (ou simplement Pj lorsqu’il n’y a pas d’ambigu¨ıté). En outre, à l’image de BT D, la décomposition induit un ordre de choix de variables partiel comme cela a été décrit dans la sous-section 4.2.2. En particulier, si le cluster racine Er = Eg dans la figure 6.1, l’ordre partiel de choix de variables est : Λ = [{x1, x4, x5}, {{x2, x3}, [{x8, x9}, {{x6, x7}, [{x10, x11}, {x12, x13, x14}], [{x15, x16}, {x17, x18, x19}]}]}]. Lorsqu’un cluster Ei est totalement assigné, pour chaque cluster Ej dans F ils(Ei), le sous-problème Pj |A[Ei ∩ Ej ] est résolu indépendamment. Comme dans le cas du problème de décision o`u BT D enregistre le résultat de l’exploration du problème Pj |A[Ei ∩ Ej ] (enregistrement de goods et de nogoods), #BT D évite certaines redondances en enregistrant également les informations nécessaires. En particulier, #BT D enregistre le nombre exact de solutions d Pj |A[Ei ∩ Ej ], noté #solEj , comme un #good structurel(A,#solEj ). Ce faisant, le nombre de solutions ne sera jamais recalculé pour la même affectation Ei ∩ Ej . C’est ainsi que #BT D, comme BT D, est capable de maintenir une complexité exponentielle en fonction de la taille du plus grand cluster de la décomposition. #BT D est décrit dans l’algorithme 6.1. Etant donnés une affectation ´ A et un cluster Ei , #BT D cherche le nombre d’extensions cohérentes B de A sur Desc(Ei) telles que A[Ei\VEi ] = B[Ei\VEi ]. Le premier appel réalisé est #BT D(P,(E, T), ∅, Er, Er, ∅) et retourne le nombre de solutions du problème global. #BT D commence par assigner les variables du cluster racine. Si, dans l’exemple de la figure 6.1, Er = Eg, les premières variables à assigner sont les variables x1, x4 et x5. Au sein de chaque cluster à affecter, #BT D procède classiquement en assignant une valeur à une variable et en faisant un retour-arrière si la recherche rencontre une incohérence (lignes 15-22). Des algorithmes tels que #BT, #MAC ou #RF L peuvent être utilisés. La présentation est basée sur #BT. Soit Ei le cluster courant. Une fois toutes les variables de Ei instanciées de façon cohérente (ligne 1), #BT D calcule le nombre de solutions du sous-problème induit par chaque cluster fils de Ei , s’il en a (lignes 2-12). Dans le cas de la figure 6.1, Ei possède 3 fils : En, Ej et El . Considérons par exemple le cluster fils Ej . Etant donnée une affectation courante ´ A de Ei , #BT D vérifie d’abord si l’affectation A[Ei ∩ Ej ] correspond à un #good (ligne 7). Si A[Ei ∩ Ej ] est effectivement un #good, #BT D multiplie le nombre de solutions enregistré avec le nombre de solutions de Ei avec A comme affectation (ligne 8). Sinon, #BT D étend A sur les variables restantes de Desc(Ej ) dans le but de calculer le nombre d’extensions cohérentes #solEj (ligne 10). Les variables impliquées dans le cas de la figure 6.1 sont x10, x11, x12, x13 et x14.

Inconvénient de #BTD

La façon dont #BT D procède pour calculer le nombre de solutions d’un problème peut effectivement engendrer des calculs coˆuteux et inutiles. L’idée de base est qu’étant donnée une affectation partielle A, un appel à #BT D, comme celui de #solEj ← #BTD(P, (E, T), A, Ej , VEj \(Ei ∩ Ej )) (ligne 10), compte toutes les solutions du sous-problème courant. Pour autant BT D n’a pas la garantie que l’affectation partielle s’étend à une solution sur tout le problème. Nous illustrons cet inconvénient de #BT D sur l’exemple de la figure 6.1. Soit Er = Eg le cluster racine de la décomposition par lequel #BT D débute le comptage. Supposons que Ei est le cluster courant et qu’il vient d’être instancié d’une façon cohérente (Eg et Eh sont déjà instanciés). #BT D traite alors les clusters fils de Ei l’un après l’autre en calculant le nombre exact de solutions correspondant à chaque sous-problème enraciné en chaque cluster fils. Il considère, par exemple, le cluster Ej et calcule le nombre exact de solutions du problème Pj |A[Ei ∩ Ej ], puis considère le cluster El et calcule celui de Pl |A[Ei ∩ El ] et enfin considère le cluster En afin de calculer celui de Pn|A[Ei ∩ En]. L’inconvénient d’une telle approche est que toutes les solutions de Pj |A[Ei ∩ Ej ] sont calculées avant de s’assurer qu’il existe au moins une solution pour Pl |A[Ei ∩ El ] et pour Pn|A[Ei ∩ En]. Plus précisément, le nombre de solutions d’un sous-problème donné est calculé avant de vérifier que l’affectation courante peut s’étendre en une solution globale, c’est-à-dire une affectation cohérente de toutes les variables du problème. En effet, dans le pire des cas, #BT D pourrait calculer le nombre de solutions de Pj |A[Ei ∩ Ej ] et de Pl |A[Ei ∩ El ] avant d’établir que Pn|A[Ei ∩ En] ne possède aucune solution. Dans ce cas, le nombre de solutions calculé et enregistré pour les sous-problèmes Pj |A[Ei ∩ Ej ] et Pl |A[Ei ∩ El ] s’avère inutile (sauf si le #good enregistré pour un sous-problème est utilisé ultérieurement). La situation devient de plus en plus pénalisante pour #BT D lorsque le nombre de sous-problèmes examinés avant l’exploration du sous-problème pour lequel il n’existe aucune extension cohérente augmente. Pour résumer, #BT D n’exploite pas le fait qu’il est inutile de compter le nombre d’extensions d’une affectation sur un sousproblème si cette affectation ne s’étend pas en une solution globale, c’est-à-dire une solution du point de vue du problème de décision. Ce principe s’applique aussi localement pour un sous-problème en particulier. C’est ainsi que pour compter le nombre d’extensions cohérentes d’une affectation donnée de Ei sur Desc(Ei), il est inutile de compter le nombre d’extensions cohérentes de cette affectation pour un fils donné de Ei si elle n’admet pas au moins une extension sur toutes les variables de Desc(Ei). En conséquence, cet inconvénient peut détériorer l’efficacité de #BT D vu que des sous-espaces de recherche sont explorés inutilement ce qui consomme du temps mais aussi de l’espace mémoire en enregistrant des informations qui ne seront éventuellement pas réutilisées par la suite. Ainsi, une première possibilité pour améliorer #BT D consiste à éviter ces recherches inutiles. Dans la section suivante, nous exploitons cette idée dans le but de définir un algorithme plus sophistiqué que nous appellerons #EBT D. Ce travail a fait l’objet de la publication [Jégou et al., 2016a]