Adaptation au contexte de la résolution dans le cadre WCSP 

Adaptation au contexte de la résolution dans le cadre WCSP 

Nous présentons dans cette partie les objectifs de l’utilisation dynamique de la décomposition pour la résolution d’instances WCSP. Tout d’abord, l’utilisation dynamique de la décomposition pour la résolution d’instances WCSP rejoint le but de la fusion dynamique employée dans le cadre CSP qui consiste à améliorer l’exploitation des approches adaptatives dans les méthodes structurelles. D’ailleurs, l’emploi d’une décomposition arborescente pour la résolution des instances WCSP pose le même problème que son exploitation pour la résolution des instances CSP en termes de liberté de l’heuristique de choix de variables. En permettant des ordres partiels non compatibles avec la décomposition d’origine, tout en étant moins contraignants, nous augmentons la chance de l’algorithme de trouver un ordre de choix de variables plus opportun à l’égard de l’instance à résoudre. Par exemple, en ayant le maximum de liberté, une heuristique de choix de variables telle que dom/wdeg est plus susceptible de localiser plus rapidement les parties les plus difficiles de l’espace de recherche. En plus de leur association avec les approches adaptatives, les algorithmes de résolution des instances WCSP ont connu une amélioration remarquable au niveau de leur stratégie de recherche. Plus précisément, avec HBF S, la combinaison des deux stratégies de recherche, à savoir le parcours en profondeur (DF S) et le parcours du meilleur d’abord (BF S) a amélioré significativement la résolution des problèmes d’optimisation sous contraintes [Allouche et al., 2015] (cf. la partie 2.4.4.1). Naturellement, si les limitations imposées par la décomposition au niveau de l’heuristique de choix de variables sont drastiques, l’efficacité pratique de cette hybridation peut s’en retrouver détériorée. Ainsi, relˆacher les contraintes imposées par la décomposition offre l’opportunité d’avoir une plus grande sélection de variables lors du choix de la prochaine variable à instancier. Par conséquent, une variable de meilleure borne inférieure peut être trouvée lorsque BF S est exploité. Ensuite, l’utilisation dynamique de la décomposition pour la résolution d’instances WCSP vise à capturer des instances résolues facilement, voire trivialement, par des méthodes non structurelles. En effet, selon la nature de l’instance à résoudre, il se peut que l’instance soit résolue en quelques fractions de secondes par une méthode comme DF S ou HBF S tandis qu’elle nécessiterait des heures d’exécution avant d’être résolue par une méthode basée sur BT D. Pour y parvenir, la méthode proposée devrait pouvoir supprimer dans certains cas toute contrainte imposée sur l’heuristique de choix de variables afin de lui permettre d’acquérir une liberté totale. L’exploitation dynamique de la décomposition vise également à permettre la résolution de certaines instances plus difficiles, habituellement résolues par une exploitation classique de la décomposition. Plus précisément, elle vise à exploiter les indépendances détectées entre les sous-problèmes ainsi que les enregistrements pouvant être réalisés. Afin d’atteindre cet objectif, la méthode proposée devrait pouvoir se comporter dans certains cas comme une méthode classique basée sur BT D. La combinaison des avantages des méthodes structurelles et non structurelles a aussi pour objectif de résoudre de nouvelles instances en exploitant conjointement les avantages des méthodes non structurelles et ceux des méthodes structurelles. A cette fin, l’exploita- ` tion dynamique de la décomposition devrait permettre d’exploiter la décomposition d’une façon plus légère que son exploitation classique sans toutefois perdre tout l’intérêt des méthodes à base de décomposition. En outre, au vu de l’efficacité des approches adaptatives et de la grande variété d’instances ciblées par l’exploitation dynamique de la décomposition, cette dernière vise à s’adapter à la nature de l’instance afin que la décomposition couramment employée soit la plus opportune possible. Il peut s’agir de la décomposition d’origine, d’une décomposition formée d’un seul cluster ou d’une décomposition intermédiaire. Son but est alors de se baser sur l’historique de l’instance et sur son état actuel afin de décider quelle décomposition utiliser. Finalement, l’utilisation dynamique de la décomposition permet d’attribuer moins d’importance à la décomposition originale calculée. En effet, dans le chapitre 3, nous nous sommes intéressés à la qualité de la décomposition calculée vis-à-vis de la résolution. Nous avons aussi vu que selon la décomposition utilisée pendant la résolution, cette dernière peut être plus ou moins efficace. Permettre de se libérer de cette décomposition initialement calculée atténue les inconvénients de celle-ci s’il s’avère qu’elle est à l’origine de la détérioration de l’efficacité de la résolution. 

Exploitation de la décomposition ≪ si besoin ≫ pour le problème WCSP : BTD-DFS+DYN 

Dans le même esprit des travaux réalisés pour le problème CSP dans le chapitre 4, nous visons dans cette partie à exploiter le concept de dynamicité de la décomposition pour le problème WCSP. Comme évoqué dans la partie précédente, nous visons à profiter de l’efficacité des heuristiques de choix de variables adaptatives comme l’heuristique dom/wdeg et du progrès réalisé par les algorithmes de recherche à parcours hybride comme HBF S. Ainsi, nous tentons de libérer les méthodes exploitant une décomposition. En revanche, l’utilisation d’une décomposition peut être parfois très bénéfique pour la résolution des instances WCSP. En particulier, l’enregistrement des informations au niveau des séparateurs entre clusters permet d’élaguer des parties de l’espace de recherche et de rendre la résolution plus efficace. Ces enregistrements permettent de mémoriser, pour chaque sous-problème considéré, les meilleures bornes inférieures et supérieures calculées, ou mieux encore, son optimum. La question qui se pose légitimement est alors de savoir comment exploiter conjointement les avancées dont ont bénéficié les algorithmes de recherche au niveau des heuristiques de choix de variables et du type de parcours pour le problème WCSP et les avantages offerts par la décomposition arborescente. Afin de concilier ces deux points de vue, nous proposons dans cette partie d’exploiter la décomposition dynamiquement d’une façon plus flexible et plus appropriée et adaptée au vu du contexte courant de la résolution. Cela permet de s’adapter progressivement à la nature de l’instance à résoudre. La forme de dynamicité que nous proposons dans ce cadre consiste à utiliser la décomposition correspondant à un sous-problème uniquement lorsque la recherche sans décomposition semble stagner. La décomposition arborescente est alors exploitée d’une façon plus adéquate en évitant de l’utiliser systématiquement que ce soit globalement sur tout le problème ou localement sur un sous-problème. Ainsi, nous proposons dans ce qui suit l’algorithme BT D-DF S+DY N qui intègre ce type de fonctionnement. Il est très important de noter qu’au vu de l’efficacité pratique de BT D-HBF S par rapport à celle de BT D-DF S [Allouche et al., 2015], nous sommes naturellement plus intéréssés par BT D-HBF S+DY N que par BT D-DF S+DY N. Toutefois, nous présentons dans cette partie BT D-DF S+DY N par souci de simplicité. Cependant, l’extension de BT D-HBF S peut être déduite sans difficulté de celle de BT D-DF S. L’algorithme BT D-DF S+DY N (voir l’algorithme 5.1) se base sur l’algorithme BT DDF S. Les modifications apportées représentent une adaptation de l’algorithme afin de prendre en compte l’exploitation dynamique de la décomposition. Les deux algorithmes se basent sur une décomposition arborescente calculée en amont de la résolution et qui est enracinée en un cluster Er. En ce qui concerne BT D-DF S, la décomposition induit classiquement un ordre partiel sur les variables comme tous les algorithmes basés sur BT D et comme nous l’avons déjà vu dans la partie 4.2.2. Cependant, BT D-DF S+DY N exploite la décomposition différemment. 

Décomposition si besoin

BT D-DF S+DY N a pour objectif d’exploiter la décomposition à bon escient, c’est- à-dire quand le besoin s’en fait sentir. Plus précisément, la décomposition calculée initialement ne sera exploitée, pour un sous-problème donné, que si la résolution sans décomposition est jugée inefficace. Prenons l’exemple de la décomposition de la figure 4.1 du chapitre 4 représentée par l’ensemble de clusters E = {Ei , Ej , Ek, El , Em, En} enracinée en Ei . Soit Ej le cluster courant et A l’affectation courante. Nous nous intéressons au sous-problème Pj |A enraciné en Ej induit par l’affectation A du séparateur Ei ∩ Ej avec Ei le cluster parent de Ej . La résolution du sous-problème Pj |A n’utilisera pas forcément la décomposition, soit l’ensemble des clusters {Ej , Ek, El , Em, En}. En effet, au début, la résolution est basée sur le cluster E∗ j résultant de la fusion du cluster Ej avec ses descendants Ek, El , Em et En. D’o`u, formellement E∗ j = ∪Ep∈Desc(Ej )Ep. Cette fusion consiste en une mise en commun de toutes les variables des clusters de la descendance de Ej (voir figure 5.1). Ainsi E∗ j contient toutes les variables des clusters descendants de Ej , Ej inclus. En ce qui concerne l’heuristique de choix de variables, elle acquiert une liberté totale quant au choix des variables suivantes sur E∗ j . Plus précisément, l’ordre partiel induit par la décomposition est : Λ = [{x1, x2}, {x3, x4, x5, x6, x7, x8, x9, x10, x11}]. A ce niveau, deux cas se présentent : ` • Le sous-problème Pj |A est facilement résolu en se basant sur E∗ j . Dans ce cas, l’exploitation de la décomposition ne semble pas utile et ne sera pas exploitée. • La résolution de Pj |A est au contraire inefficace. Dans ce cas, l’exploitation de la décomposition semble judicieuse. Le cluster Ej est alors réexploité et le même raisonnement est répété au niveau du cluster Ek qui sera au début considéré fusionné avec les clusters de sa descendance formant le cluster E∗ k comme le montre la figure 5.2. L’ordre partiel ainsi induit par la décomposition est alors : Λ = [{x1, x2}, {x3, x4, x5}, {x6, {x7, x8, x9, x10, x11}}] Quant aux clusters feuilles (n’ayant pas de fils comme En), BT D-DF S+DY N se comporte comme BT D-DF S. A noter que ce raisonnement est répété pour chaque nouvelle ` affectation de Ei ∩ Ej . Ce choix est motivé par le fait qu’une affectation A du séparateur Ei ∩ Ej induit un sous-problème différent de celui induit par une affectation A′ . A noter ` aussi qu’au niveau du cluster racine, BT D-DF S+DY N se comporte comme l’algorithme de base ayant toute la liberté concernant le choix des variables du problème. Finalement, la décomposition initiale est utilisée complètement (tous ses clusters sont exploités) si à tous les niveaux BT D-DF S+DY N décide d’exploiter le cluster lui-même plutˆot que sa descendance. 

Description de l’algorithme BTD-DFS+DYN

 Nous décrivons dans cette sous-section l’algorithme BT D-DF S+DY N en mettant en avant les similitudes avec BT D-DF S ainsi que les modifications qui y sont apportées. 5.3.2.1 Similitudes avec BTD-DFS L’algorithme BT D-DF S+DY N prend en paramètres l’affectation courante A, le cluster courant Ei , l’ensemble VEi des variables non affectées de Ei , l’ensemble Vdesci des variables non affectées de la descendance Desc(Ei) de Ei et les bornes inférieure et supérieure courantes clb et cub. Il vise à calculer l’optimum du problème enraciné en Ei et induit par l’affectation A. Lorsque l’optimum est calculé, la valeur de cub retournée correspond à ce dernier. Par souci de clarté, le paramètre cub donné en entrée sera noté cube et celui en sortie sera désigné par cubs . Deux cas sont possibles : • Si la valeur de cubs est strictement inférieure à celle de cube , alors cubs est l’optimum correspondant à ce sous-problème. • Sinon, cubs définit une borne inférieure de l’optimum. L’appel initial est BT D-DF S+DY N(∅, Er, VEr , Vdescr , lb(Pr|∅), k) avec Vdescr l’ensemble des variables de la descendance de Er, lb(Pr|∅) la borne inférieure initiale déduite grˆace à l’application de la cohérence locale au problème initial et k le coˆut maximal. Rappelons que tout au long de l’algorithme, w i ∅ désigne la borne inférieure localisée relative au cluster Ei . Comme BT D-DF S, BT D-DF S+DY N suppose que le problème donné en entrée est cohérent selon la cohérence locale utilisée et renvoie son optimum. Les lignes 5 à 17 de BT D-DF S+DY N visent à instancier les variables de V ′ comme le ferait BT D-DF S pour les variables de VEi . Un couple (variable, valeur), (x, v), est sélectionné selon les heuristiques de choix de variables et de valeurs employées. Comme le type de branchement utilisé est binaire, ce choix se décline en deux branches x = v (ligne 9) et x 6= v (ligne 14). Pour chaque branche, la cohérence locale est appliquée au sous-problème enraciné en Ei et induit par l’affectation courante permettant d’obtenir une borne inférieure lb(Pi |A ∪ {(x = v)}) si une décision positive est faite et lb(Pi |A ∪ {(x 6= v)}) sinon (cf. la partie 2.4.4.2 et l’algorithme Lc-BT D+ pour de plus amples détails). Si le maximum clb′ entre la borne inférieure lb(Pi |A ∪ {(x = v)}) (ou lb(Pi |A ∪ {(x 6= v)}) lorsqu’il s’agit d’une décision négative), déduite par la cohérence locale, et la borne inférieure courante clb, est toujours inférieure à cub, la recherche continue ; sinon le sous-arbre correspondant est élagué. Les lignes 20 à 27 de BT D-DF S+DY N résolvent les sous-problèmes enracinés en chaque cluster fils Ej de Ei de la même façon que BT D-DF S. Le sous-problème Pj |A n’est exploré que si son optimum n’est pas déjà connu. D’ailleurs, BT D-DF S et BT DDF S+DY N mémorisent pour chaque sous-problème Pj |A deux valeurs, notées LBPj |A et UBPj |A, représentant respectivement les meilleures bornes inférieure et supérieure connues pour Pj |A. Si LBPj |A = UBPj |A, l’optimum de Pj est déjà calculé. L’appel récursif correspondant au fils Ej (ligne 25) exploite une borne supérieure initiale non triviale calculée à la ligne 24 comme expliqué dans [Givry et al., 2006]. Plus précisément, bien que l’utilisation d’un majorant initial trivial (k dans ce cas), garantisse effectivement que l’optimum de Pj |A sera correctement calculé, cela ne permet pas d’élaguer efficacement l’espace de recherche en n’ayant pas une coupe initiale efficace. En outre, en résolvant le sous-problème Pj |A indépendamment des autres sous-problèmes, nous pourrons détériorer l’efficacité de la résolution. En effet, l’optimum trouvé pour Pj |A additionné aux coˆuts des clusters déjà affectés et aux bornes inférieures calculées pour d’autres, peut éventuellement largement dépasser la borne supérieure courante et ne pas ainsi être capable de participer à une solution globale. Ainsi, Pj |A exploite une borne supérieure non triviale qui est le minimum entre la meilleure borne supérieure enregistrée pour ce problème UBPj |A et une deuxième borne supérieure déduite de la différence entre la borne supérieure courante cub et le minorant de Pi |A duquel nous retranchons le minorant de Pj |A. En exploitant cette nouvelle borne supérieure, si une solution de coˆut strictement inférieur à cette borne est trouvée, l’optimum est ainsi trouvé. Sinon, nous pouvons uniquement déduire une borne inférieure de l’optimum. L’appel récursif est suivi par une mise à jour de LBPj |A et de UBPj |A (ligne 26). En effet, si à la ligne 25 l’optimum est trouvé, les valeurs de LBPj |A et UBPj |A seront toutes les deux égales à l’optimum. Sinon, LBPj |A sera mis à jour en fonction de la nouvelle borne inférieure trouvée. L’exploration de tous les clusters fils permet enfin de mettre à jour cub (ligne 27). Cette mise à jour se fait en prenant le minimum entre la borne supérieure courante cub et celle déduite de la somme du coˆut de l’affectation courante du cluster Ei représenté par w i ∅ et des meilleures bornes supérieures UBPj |A trouvées pour chaque sous-problème Pj |A.