Modification dynamique de la décomposition via la fusion

Modification dynamique de la décomposition via la fusion pour le problème CSP

BTD-MAC+RST+Fusion Nous visons à offrir à BT D plus de liberté quant à l’heuristique de choix de variables et à ne pas se contenter du niveau de liberté actuellement existant. La thèse que nous défendons ici est que la dynamicité de la décomposition i.e. sa modification pendant la résolution, permet d’adapter la décomposition à la nature de l’instance à résoudre. Par sa modification, nous visons la modification de l’ensemble de clusters E exploités. L’opération permettant de changer la décomposition dans ce contexte est la fusion des clusters. Dans ce qui suit, nous proposons l’algorithme BT D-MAC+RST+F usion permettant d’intégrer la modification dynamique de la décomposition via la fusion des clusters. Ces travaux ont fait l’objet des publications [Jégou et al., 2016b,c]. L’algorithme BT D-MAC+RST+F usion (voir l’algorithme 4.2) représente une adaptation de l’algorithme BT D-MAC+RST [Jégou and Terrioux, 2014a] (cf. la partie 2.2.5.1) afin de prendre en compte la fusion dynamique. Pour ces deux algorithmes, la décomposition arborescente est calculée en amont de la résolution. Comme décrit dans la section 4.2.2, l’emploi de cette décomposition enracinée en un cluster Er induit un ordre partiel sur les variables. La différence principale entre eux réside dans le fait que BT D-MAC+RST utilise cette décomposition initiale durant toute la résolution (au sens de l’ensemble des clusters qui la définissent puisque la racine peut changer), tandis que BT D-MAC+RST+F usion va la faire évoluer dynamiquement. Ainsi, l’ordre partiel imposé par la décomposition change pendant la résolution. Nous donnons tout d’abord des détails plus amples sur la fusion dynamique.

Fusion dynamique

 La fusion consiste à mettre en commun les variables de deux clusters voisins pour former ainsi un seul cluster. La figure 4.2 montre la fusion des clusters Ej et Ek de la décomposition de la figure 4.1. Le cluster résultant de la fusion du cluster Ej et du cluster Ek est un nouveau cluster Ej . Il est à noter que, les fils du cluster fusionné deviennent les fils du cluster résultant de la fusion. Par exemple, dans la figure 4.1, El et Em, les fils de Ek, deviennent les fils de Ej qui est le cluster résultant de la fusion des clusters Ej et Ek dans la figure 4.2. La figure 4.3 montre à son tour l’arbre T correspondant aux décompositions avant et après la réalisation de la fusion. Soit D la décomposition initiale et D′ la décomposition après la fusion. Pour le meme cluster racine, tout ordre sur les variables permis par D reste permis par D′ . Cependant, en exploitant D′ nous pouvons obtenir plus d’ordres possibles qu’en exploitant D. Nous en déduisons que la fusion préserve les ordres de choix de variables initialement permis tout en offrant plus de liberté. Par exemple, pour Er = Ei , si l’ordre partiel induit par la décomposition dans la figure 4.1 est : [{x1, x2}, {x3, x4, x5}, {x6, [{x7, x9}, {x8, {x10, x11}}]}], l’ordre partiel induit par la décomposition dans la figure 4.2 est : [{x1, x2}, {x3, x4, x5, x7, x9}, {x6, x8, {x10, x11}}]. Ainsi, l’ordre [x1, x2, x7, x9, x3, x4, x5, x6, x8, x10, x11] est par exemple désormais permis par la décomposition de la figure 4.2 alors qu’il ne l’était pas auparavant par la décomposition de la figure 4.1. Le choix de fusionner ou non des clusters est conditionné par des informations apprises durant la résolution. Aussi, le comportement de BT D-MAC+RST+F usion se situe entre celui de BT D-MAC+RST avec une liberté partielle pour l’ordre sur les variables (si aucune fusion n’est effectuée) et celui de MAC+RST avec une liberté totale (si, après une série de fusions, la décomposition ne contient plus qu’un seul cluster). L’intérˆet de ce nouvel algorithme est de pouvoir trouver dynamiquement le bon compromis à partir d’informations recueillies durant la résolution. En d’autres termes, son but consiste à exploiter les informations fournies durant la résolution pour adapter en permanence la décomposition et ainsi la liberté de choix de variables au contexte courant de la résolution. La différence primordiale entre la fusion dite statique [Jégou et al., 2005] et la fusion dynamique réside dans la raison du déclenchement de la fusion des clusters. La fusion dynamique est réalisée pendant la résolution en se basant sur des informations récoltées depuis le début de la résolution jusqu’au moment de la fusion. La fusion statique est faite au préalable de la résolution. Elle se fait habituellement sur la base de critères purement structurels avec tous les inconvénients que cela peut comporter. Par exemple, le but de la fusion statique pourrait consister à limiter la taille des séparateurs en supprimant ceux dans la taille dépasse la limite choisie via la fusion des deux clusters impliqués. D’autres objectifs peuvent ˆetre visés comme la création de clusters connexes ou l’augmentation du nombre de variables propres de chaque cluster. 

Description de l’algorithme BTD-MAC+RST+Fusion 

Similitudes avec BTD-MAC+RST 

L’algorithme BT D-MAC+RST+F usion exploite l’algorithme BT D-MAC+F usion (voir l’algorithme 4.1). Ce dernier ne se différencie de BT D-MAC (cf. la partie 2.2.5.1) que par les lignes 17 à 21. Initialement, la suite de décisions Σ ainsi que les ensembles de goods Gd et de nogoods Nd sont vides. BT D-MAC+RST+F usion (à l’instar de BT D+MAC+RST) commence la résolution en assignant les variables du cluster Er avant de passer à un cluster fils. En exploitant le nouveau cluster Ei , seules les variables non assignées du cluster Ei seront instanciées. En d’autres termes, seules les variables de Ei n’appartenant pas à Ei ∩ Ep(i) sont instanciées. Pour résoudre chaque cluster les deux algorithmes s’appuient sur MAC (lignes 24-29 et 35-37). Durant la résolution MAC peut prendre deux types de décisions : • Décisions positives xi = vi qui assignent la valeur vi à la variable xi (ligne 27), • Décisions négatives xi 6= vi qui assurent que vi ne peut ˆetre assignée à xi (ligne 35). Supposons que Σ =< δ1, . . . , δi > est la suite de décisions courante o`u chaque δj peut ˆetre une décision soit positive, soit négative. Une nouvelle décision positive xi+1 = vi+1 est prise et un filtrage par cohérence d’arc (AC) est accompli (ligne 27). Si aucune incohérence n’est détectée, la recherche continue normalement (ligne 28). Sinon la valeur vi+1 est supprimée de Dxi+1 et un nouveau filtrage par AC est effectué (ligne 35). Si une incohérence est détectée, nous procédons à un retour-arrière et la dernière décision positive xl = vl est changée en xl 6= vl . Lorsque le cluster Ei est choisi comme cluster suivant, nous savons que la prochaine décision positive implique une variable de Ei . Etant donné que le séparateur ´ Ei ∩ Ep(i) est instancié, le filtrage par AC impacte uniquement les variables des clusters de Desc(Ei). Une fois le cluster Ei complètement instancié de fa¸con cohérente (ligne 1), chaque sous-problème enraciné en un cluster Ej , fils de Ei , sera résolu (ligne 11). Plus précisément, pour un cluster fils Ej et une suite de décisions Σ, nous résolvons le problème enraciné en Ej et induit par P os(Σ)[Ei∩Ej ] o`u P os(Σ)[Ei∩Ej ] est l’ensemble des décisions positives impliquant les variables de Ei ∩ Ej dans Σ. Si nous trouvons une extension cohérente de Σ sur Desc(Ej ), P os(Σ)[Ei ∩ Ej ] est enregistré comme good structurel (ligne 12-13). Si, au contraire, la résolution montre qu’il n’existe aucune extension cohérente de Σ sur Desc(Ej ), P os(Σ)[Ei ∩ Ej ] est enregistré comme un nogood structurel (lignes 15-16). Ces (no)good structurels sont utilisés ultérieurement dans la recherche pour éviter certaines redondances (lignes 7-8 et 10). Si un redémarrage est déclenché (ligne 31), la résolution est interrompue. La gestion des redémarrages est faite comme dans [Jégou and Terrioux, 2014a] et s’accompagne de l’enregistrement de nld-nogoods réduits [Lecoutre et al., 2007e] qui permettent de ne pas réexplorer des parties de l’espace de recherche déj` visitées. L’intérˆet du redémarrage réside dans l’exploitation des connaissances acquises auparavant via les (no)good structurels et les nld-nogoods réduits [Lecoutre et al., 2007e]. Le déclenchement d’un redémarrage peut ˆetre conditionné par des paramètres globaux (portant sur l’ensemble du problème) ou locaux (relatifs au cluster courant) ou aussi une combinaison des deux. Pour plus de détails sur les redémarrages sous BT D, nous invitons les lecteurs à se référer à la partie 2.2.5.1 ou aux travaux cités ci-dessus. 

Modifications réalisées pour BTD-MAC+RST+Fusion 

Les lignes 17-21 concernent uniquement la fusion dynamique donc BT D-MAC+F usion. La fusion dynamique vise, comme expliqué ci-dessus, à donner plus de liberté à l’heuristique de choix de variables, et en meme temps, à limiter l’impact des défauts potentiels mis en avant dans la partie 4.2.2. Le choix de fusionner ou non des clusters va se faire sur la base des critères s’appuyant sur l’état courant du problème, mais aussi sur tout ou partie des états précédemment rencontrés durant la résolution. Ce choix est implémenté via la fonction fusion qui retourne vrai si une fusion est nécessaire et f aux sinon. Cette fonction peut ˆetre librement implémentée par l’utilisateur qui pourrait intégrer les critères qu’il souhaite faire entrer en jeu dans la décision de la fusion ou de la non-fusion des clusters. Si aucune fusion n’est requise (fusion renvoie f aux), la résolution se poursuit normalement. Au contraire, si ce critère considère que fusionner le cluster courant avec un de ses fils permettrait de rendre la suite de la résolution plus efficace (par exemple en permettant d’instancier plus tˆot certaines variables jouant un rˆole clé), fusion renvoie vrai et BT D-MAC+F usion va modifier la décomposition courante en fusionnant ces deux clusters (ligne 18). La figure 4.4 montre l’affectation des variables du cluster Ej (les variables affectées sont colorées en rouge). Supposons, par exemple, qu’après l’affectation de la variable x4, la fonction fusion retourne vrai pour le cluster Ek. La décomposition va alors ˆetre modifiée et les clusters Ej et Ek fusionnés. Pour cela, nous commen¸cons par désaffecter les variables instanciées du cluster courant et par enregistrer des nld-nogoods réduits (ligne 32) comme le ferait un redémarrage classique. Dans la figure 4.5, les variables x3 et x4 sont alors désaffectées et la recherche retourne au cluster Ei . Une fois revenu dans le cluster parent, nous procédons à la fusion. A ce stade (ligne 19), soit nous continuons à ` revenir en arrière si redemarrage ´ est vrai, soit la recherche se poursuit avec l’exploration d’un fils du cluster parent. Par exemple, la figure 4.6 montre que BT D-MAC+F usion explore le nouveau cluster Ej et est désormais capable d’affecter d’abord les variables x7 et x9. Notons que désaffecter les variables du cluster courant avant de le fusionner avec un de ses fils n’est pas une nécessité. Toutefois, ce choix devrait permettre d’exploiter au plus tˆot les variables nouvellement ajoutées dans ce cluster. L’algorithme BT D-MAC+F usion est paramétrable notamment par l’heuristique de fusion (nous en proposons une dans la partie expérimentale). Un bon choix pour cette heuristique devrait permettre d’améliorer considérablement la résolution en la rendant plus efficace.