Actes JFPC 2005

Implémenter des contraintes globales expliquées

1,2 2
Guillaume Rochart Narendra Jussien
1
École des Mines de Nantes – LINA CNRS FRE 2729
4 rue Aflred Kastler – BP 20722 – F-44307 Nantes Cedex 3, France
2
e-lab – Bouygues SA
1 av Eugène Freyssinet – F-78280 Guyancourt, France
grochart@[Link] jussien@[Link]

Résumé cessus industriels et en optimiser les revenus, la qua-

Modifier le comportement d’un solveur de lité ou l’ergonomie : gestion du personnel, optimisation
contraintes pour lui ajouter de nouvelles capacités est d’un parc de machines, emploi du temps (des universi-
souvent une tâche complexe : l’optimisation extrême, tés aux formations d’employés), etc. Cependant, dans
fruit d’une expérience de développement de plusieurs les outils actuels, lorsqu’il n’est pas possible de trouver
années, du cœur de propagation et des algorithmes de une solution (car toutes les contraintes dures – qui ne
filtrage rend cette opération particulièrement délicate peuvent être remises en cause – forment un problème
si on souhaite maintenir le niveau de qualité atteint sur-contraint) il est rarement possible d’en connaı̂tre la
par l’outil. Dès lors, cette difficulté constitue bien
cause. De même, il est pratiquement impossible dans
souvent un frein pour mettre en place au sein du
les solveurs de simuler après résolution le retrait d’une
solveur de nouvelles techniques ou outils (explications,
trace précise, etc.). Nous montrons dans cet article ou plusieurs contraintes pour modifier le problème afin
les problèmes posés par l’ajout d’explications dans des d’améliorer les solutions trouvées.
contraintes globales et proposons deux nouvelles mé- Cette problématique n’est d’ailleurs pas propre à la
thodes pour ajouter des contraintes globales expliquées programmation par contraintes ni même aux outils de
dans un solveur : l’une basée sur l’utilisation d’un cadre résolutions de problèmes combinatoires, mais consti-
générique de description des contraintes globale, l’autre tue un domaine de recherche en intelligence artificielle,
utilisant les possibilité de la programmation par aspects.
cherchant à expliciter le résultat retourné par un lo-
Abstract giciel. L’abduction, ou la recherche d’explication, dans
Adding new features to a constraint solver may be le cadre de la programmation par contraintes, consiste
a tedious and difficult task. Indeed, propagation engines en particulier à fournir des outils ou à instrumenter un
and filtering algorithms have been optimized for a long algorithme pour permettre la génération, le maintien
time, by numerous developers. To modify them without et le stockage d’ensembles d’informations permettant
decreasing the quality of the software, one has to check de justifier logiquement un état courant du système
that the new feature will not interfere with previous (comme une contradiction, une valeur de la fonction
works. This is why developing new features like on-the-
objectif, etc.). Mais générer de telles explications, les
fly explanations or new trace formats can be hard and
long to add in a commercial constraint solver, even it is
exploiter et les rendre accessibles à l’utilisateur final
well known that these features can be very useful for the peut nécessiter des modifications profondes de l’outil.
user. In this paper, we show what can be the issues when Par exemple, dans le cas de la programmation par
one wants to add explanations for global constraints and contraintes – mise à part la technique de QuickXPlain
then propose two new ways to achieve this goal. [6] qui est non intrusive mais peut coûter particuliè-
rement cher – la plupart des techniques proposées né-
1 Introduction cessite de modifier le code des contraintes, voire de
modifier l’algorithme de résolution [7]. Or, dans le cas
Pouvoir résoudre un problème combinatoire est de la programmation par contraintes, modifier le cœur
d’une grande utilité pour améliorer de nombreux pro- d’un solveur de contraintes peut se révéler très com-
pliqué voire inconcevable étant donnés les risques que contraintes concernées par les modifications ap-
cela représente pour l’entreprise vendant la solution. portées sur les variables pour que ces dernières
Nous proposons donc dans cet article plusieurs mé- puissent déduire des valeurs à retirer d’autres do-
thodes pour implémenter des contraintes globales gé- maines (grâce à un algorithme de filtrage)
nérant des explications1. Ainsi, après une brève intro- Si l’on souhaite ajouter une fonctionnalité dans un
duction sur la programmation par contraintes et les solveur de contraintes, il est souvent nécessaire de mo-
explications, nous rappelons tout d’abord des travaux difier ces deux blocs qui représentent tous les deux du
précédents [4] qui ont proposé une méthodologie pour code qui a été optimisé. Il est donc délicat, comme
modifier de manière ad hoc les contraintes (ce qui per- nous le verrons, d’ajouter de telles fonctionnalités sur
met d’obtenir des implémentations efficaces mais po- des plateformes commerciales qui demandent une forte
tentiellement coûteuses à mettre en place). Nous sou- qualité de service ou des plateformes d’une taille telle
lignerons ainsi quels sont les problèmes liés à la gé- qu’il est impossible d’ajouter du code dans toutes les
nération d’explication pour les contraintes globales. contraintes, tous les branchements, etc. C’est pourquoi
Puis nous proposons deux nouvelles solutions consis- nous proposons ici de nouvelles méthodes pour instru-
tant à utiliser d’une part, des cadres génériques de dé- menter les solveurs et les contraintes globales avec de
veloppement de contraintes globales et d’autre part, nouvelles fonctionnalités comme les explications.
la programmation par aspects pour rendre les modi-
fications indépendantes du code originel (et ainsi ne 2.2 Les explications et les algorithmes les exploi-
pas prendre le risque de mettre en péril la stabilité du tant
solveur) permettant de réduire notablement le coût de
mise en place des explications dans les solveurs. Nous Une explication est, dans le cas général, une justi-
concluons en exposant les avantages et inconvénients fication logique d’un état (problème inconsistant, do-
de chaque méthode. maine courant d’une variable, valeur de la borne du-
rant une optimisation, etc.). Dans le cadre de la pro-
grammation par contraintes, il est nécessaire de dé-
2 Contexte terminer quelles sont les hypothèses que l’on souhaite
étudier pour pouvoir justifier un état. Parmi les hy-
2.1 La programmation par contraintes
pothèses que l’on peux considérer, on peut citer par
La programmation par contraintes est une technique exemple : les domaines des variables, les choix pris par
maintenant bien connue de résolution de problèmes un algorithme de branchement, les contraintes (que
combinatoires modélisés sous la forme de problèmes l’utilisateur a posées), etc.
de satisfaction de contraintes (CSP). Un CSP se ca- Selon ce que l’on souhaite faire des explications que
ractérise par trois ensembles principaux : l’on calcule, différentes parties de ces ensembles se-
– les variables v1 , v2 , . . . vn du problème ; ront considérées comme des hypothèses. Par exemple
– leurs domaines tels que chaque variable vi doit si l’on souhaite juste conserver de l’information sur la
être instanciée à une valeur de son domaine di ; recherche pour faire une recherche intelligente, seuls
– des contraintes reliant les différentes variables. les choix du branchement nous intéressent. Par contre
Le but est alors de trouver une affectation pour chaque si l’on souhaite transmettre une information à l’utili-
variable telle que toutes les contraintes sont vérifiées sateur, la plupart du temps, les hypothèses sont les
simultanément. contraintes (c’est-à-dire quelles sont les contraintes
Pour cela, la programmation par contraintes s’ap- qui impliquent qu’un problème soit inconsistant ?).
puient sur deux phases qui coopérent : Comme les deux applications semblent intéressantes
– une phase de branchement qui consiste à se fo- et peuvent être générées de manière équivalentes, nous
caliser sur une portion de l’espace de recherche en définissons les explications à l’aide de ces deux types
prenant une décision (généralement, en affectant d’hypothèses que sont les choix pris par le branche-
une valeur à une variable) pour essayer de trouver ment et les contraintes du modèle.
une solution dans cette portion (si cela échoue un
mécanisme classique de retour-arrière est mis en Définition 1 (Explication) L’explication de l’état
place) ; X (notée expl(X)) est un sous-ensemble C
des
– une phase de propagation qui consiste à réduire contraintes du modèle C
⊆ C et un sous-ensemble
a priori l’espace de recherche en appelant les des décisions prises jusqu’à présent par l’algorithme
1 Nous nous focalisons en effet sur les contraintes globales
de branchement (di1 , . . . dim ) tels que la conjonction
de ces deux ensembles conduit logiquement à l’état X
dans cet article : d’une part, les contraintes simples sont plus
aisément instrumentables [11] et d’autre part, leur importance étant donnée la théorie de la PPC (respect des do-
dans le domaine n’est plus à démontrer. maines, des contraintes, etc.).
 Pour évaluer la qualité d’une explication, on mesure cations bien peu précises et qui n’apporteraient d’in-
sa précision. On dira ainsi qu’une explication est plus formations utiles ni à l’utilisateur (que ce soit pour
précise qu’une autre si : elle est la plus petite au sens l’utilisateur final ou le développeur) ni à l’algorithme
de l’inclusion, ou bien si elle a une plus petite car- de recherche si l’on souhaite améliorer la recherche en
dinalité, ou encore si elle est de poids agrégé le plus fournissant des explications sur les échecs.
faible (si l’on a affecté des poids aux contraintes), etc. Il est donc nécessaire de fournir des outils pour gé-
La définition souvent utilisée en programmation par nérer des explications valides (qui justifient bien logi-
contrainte est la définition de la précision au sens de quement ce que l’on souhaite) aussi précises que pos-
l’inclusion. Les résultats de ce papier ne garantissent sibles, dans un temps raisonnable (si possible une com-
pas l’optimalité de la précision des explications, mais plexité du même ordre de grandeur que le filtrage en
essaient de fournir des algorithmes déterminant natu- lui-même) et pour chaque valeur que l’algorithme de
rellement les explications les plus précises possible en filtrage peut retirer des domaines.
ce sens. Nous introduisons ici trois techniques différentes
tant au niveau de leur efficacité et de leur portée sur
2.3 La difficulté des explications pour les les différents type de problèmes à résoudre qu’au ni-
contraintes globales veau de leur coût en développement pour les mettre
en place. Nous commençons par la solution la plus évi-
L’état d’un problème de satisfaction de contraintes dente consistant à reprendre les algorithmes de filtrage
se décrit comme nous l’avons vu à l’aide des domaines, et à justifier chacun de leurs calculs [4], puis présentons
des contraintes du problème, et si l’on est en cours de deux nouvelles méthodes : l’une qui exploite les cadres
résolution des choix faits par l’algorithme de recherche. génériques de contraintes globales pour générer des ex-
Il est donc possible de justifier un état (contradiction, plications pour un nombre important de contraintes
valeur d’une borne, valeur impossible), en fonction de et adapter ces contraintes à des problématiques dy-
ces données. Il est donc possible de justifier tout état namiques, et l’autre basée sur la programmation par
du problème. aspects, une technique récente issue du génie logiciel.
Ainsi, dans le cas de contraintes simples (portant
sur un nombre de variables limité et avec des raison-
nements simples), il est aisé d’expliquer chacun des
3 Implémentation intrusive
filtrages déduits par l’algorithme de filtrage [11]. Par
La solution la plus intuitive, mais la plus coûteuse
exemple dans le cas d’une contrainte d’égalité x = y,
en temps de développement, consiste à modifier d’une
si la valeur 5 est retirée du domaine de y, alors cette
part le cœur du solveur de contraintes pour prendre en
même valeur doit être retirée du domaine x. La valeur
compte et maintenir les explications au cours de la re-
est alors retirée de x pour la même raison (explication)
cherche, et d’autre part les algorithmes de filtrage pour
que le retrait du domaine y et la contrainte d’égalité.
générer des explications à chaque fois qu’une valeur est
On voit ainsi qu’il est possible de construire incrémen-
filtrée [4]. Nous allons tout d’abord mettre en évidence
talement des explications pour chaque valeur retirée.
quelles sont les difficultés à prendre en compte lors-
Cependant on cache déjà ici la difficulté liée à cette
qu’on souhaite générer et maintenir des explications
construction incrémentale au cours de la recherche qui
avec des contraintes globales. Nous verrons comment
nécessite de modifier substantiellement l’algorithme de
surmonter ces difficultés avec les deux nouvelles solu-
branchement (cf. [8]). De plus, lorsque l’on considère
tions que nous proposons dans la suite de l’article.
une contrainte globale, un tel raisonnement devient
particulièrement compliqué. En effet, sans accéder aux
structures internes de la contrainte, il est difficile de 3.1 Expliquer chaque règle du filtrage
savoir pourquoi l’algorithme de filtrage a pris cette
La première difficulté consiste à générer les expli-
décision2 . Une solution simple serait de dire que le
cations elles-mêmes. En effet, on pourrait souhaiter,
retrait est justifié par l’état courant de tous les do-
comme dans le cas des contraintes basiques et/ou bi-
maines des variables de la contrainte et de cette der-
naires (arithmétiques par exemple), générer les expli-
nière contrainte. Cependant, ceci générerait des expli-
cations une fois que la valeur à filtrer a été trouvée. En
2 Par exemple, dans le cas de la contrainte all different : si l’on effet, il peut sembler aisé à première vue de justifier
considère quatre variables a = [[1, 4]], b = [[1, 4]], c = [[3, 4]] et le filtrage d’une valeur étant donnée la sémantique de
d = [[3, 4]] qui doivent être toutes différentes, le filtrage proposé la contrainte. C’est malheureusement rarement le cas
par [15] déduirait que a et b sont différentes toutes deux de 3
avec les contraintes globales puisque les algorithmes de
et 4. Sur un exemple aussi simple, on voit déjà qu’il n’est pas
facile de trouver a priori un algorithme général permettant de filtrage s’appuient bien souvent sur des règles subtiles.
déduire une explication précise de ces retraits de valeurs. Expliquer sans exploiter les calculs de l’algorithme de
filtrage risque donc d’impliquer soit des explications celui dans lequel on devrait être si l’on avait tout re-
peu précises, voire d’oublier des cas ou de générer des calculé statiquement avec le nouveau problème, que ce
explications qui n’en sont pas (ce qui risque de re- soit au niveau des domaines des variables (les valeurs
mettre en cause la complétude de la recherche). inconsistantes doivent être effectivement retirées, mais
De plus, même si l’on génère les explications sans celles qui sont consistantes doivent être remises dans
utiliser l’algorithme de filtrage et ses structures, il le domaine si besoin), ou au niveau de la structure de
risque d’être nécessaire d’utiliser des algorithmes très données des contraintes.
coûteux. Or le but est d’essayer, autant que possible, Pour maintenir un domaine cohérent pour les va-
de générer des explications avec des algorithmes de riables, toutes les valeurs qui ont été filtrées à cause
complexité équivalente à celles des algorithmes de fil- d’une contrainte que l’on vient de retirer sont remises
trage. dans leurs domaines respectifs. Ainsi, on est sûr de ne
C’est pourquoi il est plus prudent de reprendre les pas retirer de solutions en ignorant une valeur d’un do-
algorithmes de filtrage, comme all_different, gcc, maine injustement. Toutefois, il est alors nécessaire de
stretch, flow, etc. pour instrumenter ces algorithmes vérifier si ces nouvelles valeurs sont bien consistantes
à l’aide d’informations nécessaires à la génération d’ex- à l’aide d’une phase dite de repropagation [2].
plications. Par exemple, dans le cas de la première ver- Le deuxième problème provient du maintien des
sion de la contrainte stretch [12], l’algorithme de fil- structures de données. En effet, les structures de don-
trage s’appuie sur des calculs de bornes des blocs de nées sont souvent prévues pour fonctionner dans un
valeurs identiques et successives, et sur quelques règles algorithme de type retour-arrière, c’est-à-dire qu’une
exploitant ces bornes. Pour justifier une valeur filtrée, pile stocke les différentes valeurs attribuées à la struc-
il est donc nécessaire, d’une part de générer les explica- ture dans l’arbre de recherche. Mais si l’on résout dy-
tions justifiant les étendues minimale et maximale du namiquement un tel problème, ce mécanisme n’est plus
bloc courant et de justifier le domaine des certaines va- valable ; il est alors primordial de pouvoir réparer la
riables justifiant la règle de filtrage [17] (notamment structure de données associée à une contrainte, par
le domaine des variables voisines au bloc d’étude cou- exemple, en stockant la dernière structure consistante,
rant). et en l’adaptant au nouvel état de la recherche [4].
De même, dans le cas du all_different ou du gcc, Tous ces problèmes représentent un frein pour l’uti-
l’algorithme proposé par [15] propose de décomposer lisation des explications générées à la volée dans les
un graphe biparti reliant valeur et variable en com- solveurs de contraintes, bien qu’il s’agisse souvent
posantes fortement connexes. On peut alors prouver d’une solution intéressante car elle ne nécessite pas de
qu’une valeur qui ne se trouve pas dans la même com- nouveaux calculs, mais fournit une explication pour
posante fortement connexe que l’une des variables ne chaque problème dont il n’est pas possible de trouver
peut pas être affectée à cette variable. Pour pouvoir une solution. Nous présentons deux nouvelles solutions
filtrer cette valeur du domaine, il est donc nécessaire qui permettent de réduire ces inconvénients pour fa-
d’expliquer dans ce cas pourquoi la variable et la va- ciliter l’utilisation des explications dans des solveurs
leur n’appartiennent pas à la même composante for- utilisant non seulement des contraintes basiques, mais
tement connexe, ce qui implique bien d’instrumenter aussi des contraintes globales engendrant ces nouvelles
l’algorithme pour construire au fur et à mesure de la difficultés.
recherche des composantes cette explication [4].
4 Utilisation de cadres génériques de
3.2 Maintien de la structure dans un cadre dyna-
mique contraintes globales
Une des applications des explications est de ré- La première nouvelle solution que nous proposons
soudre des problèmes dynamiques, c’est-à-dire, dont consiste à utiliser des travaux qui proposent de four-
l’ensemble des contraintes peut varier. C’est d’ailleurs nir un cadre générique pour dériver de nombreuses
sur cette hypothèse que tient la proposition d’utili- contraintes à partir d’une description simple de celle-
ser l’algorithme mac-dbt [8], qui remplace le retour- ci soit sous la forme d’un automate [1, 13], soit sous
arrière classique par le retrait dynamique d’une des la forme de propriétés de graphes [1]. Ainsi, si l’on
contraintes responsables de l’échec actuel. accepte le surcoût lié à la perte de la complétude des
Cet aspect dynamique pose des problèmes dans la algorithmes de filtrage ou à des algorithmes moins effi-
gestion des contraintes. En effet, un problème dyna- caces, il devient possible de générer au même titre que
mique demande de retirer une contrainte sans recom- le filtrage la génération d’explications associées. Nous
mencer les calculs ; il est alors nécessaire d’assurer à commençons par présenter succinctement ces cadres
tout moment que l’on se trouve dans le même état que puis montrons comment il est possible de générer des
explications automatiquement si l’on fournit un algo-
rithme propageant ces nouvelles contraintes.
v1 = {1}

Arc vrai à cause de expl(domv1 ) ∪ expl(domv2

4.1 Les contraintes globales comme des auto-
mates ou propriétés de graphes v2 = {1}

L’univers des contraintes globales semblant infini, v3 = 1 car {contrainte} ∪ expl(domv1 )

∪expl(domv2 )
plusieurs cadres ont été proposés pour essayer de les
décrire, de les comparer, voire de dériver automatique- Fig. 1 – Exemple de génération d’explications : supposons que l’on veuille
que seules deux variables puissent avoir des valeurs égales par exemple à cause
ment l’algorithme de filtrage d’une contrainte depuis d’une contrainte de global_cardinality [16] (taille maximale des composantes de
2, avec des contraintes élémentaires d’égalité sur les arcs), et que nous étions
sa description. Parmi ces travaux on peut citer par dans l’état décrit sur le dessin (seules les variables reliées avaient des domaines
dont l’intersection était non vide), alors si v1 et v2 sont instanciées à 1, l’arc
exemple deux types de descriptions : potentiel les reliant devient présent de manière sûre (car la contrainte d’égalité
est forcément vraie), on peut donc en déduire que les autres arcs sortant de v1
– une description à base d’automates qui et v2 doivent être absent pour la même raison, à laquelle on ajoute la contrainte
en cours qui maintient la propriété de graphe. On peut alors filtrer des valeurs
consiste à simuler l’algorithme de filtrage en le depuis les variables voisines avec cette explications.

modélisant sous la forme d’un automate [13, 1] ;

ainsi, il est possible par exemple, de décrire une
d’en profiter pour générer automatiquement un grand
contrainte en fournissant un automate vérifiant
nombre de contraintes globales avec les fonctionnali-
si une solution satisfait ou non la contrainte, et
tés voulues à moindre coût (il suffit d’instrumenter les
le cadre permet d’en dériver automatiquement
contraintes élémentaires).
un algorithme de filtrage ; pour cela, le cadre
utilise un nombre bien défini de contraintes élé-
mentaires pour décrire sémantiquement le filtrage 4.2 Dériver de telles contraintes pour créer des
que l’on souhaite obtenir ; si l’on souhaite ajou- contraintes expliquées
ter une fonctionnalité comme les explications dans
les contraintes globales, il suffit alors de l’ajouter Si l’on reprend le cas du all_different et que l’on
dans ce petit noyau de contraintes élémentaires. souhaite générer des explications pour chaque retrait
– une description à base de propriétés de de valeur, il faut justifier pourquoi la contrainte a dé-
graphes qui consiste à décrire à l’aide de proprié- duit ce retrait. Pour cela, dans le cas de contraintes
tés de graphes (où schématiquement les nœuds modélisées à l’aide de propriétés de graphes, il est donc
sont des variables et les arcs des contraintes qui nécessaires d’expliquer :
peuvent être satisfaites ou non) la contrainte que – l’état des arcs (puisque à chaque arc est asso-
l’on souhaite maintenir au cours de la recherche ciée une contrainte dont la propagation dépend
[1]. Ainsi, pour modéliser l’exemple bien connu de l’état de cet arc – absent ou présent),
du all_different, il suffit de considérer chaque – la propagation de la contrainte élémentaire asso-
variable comme un nœud, de générer des arcs po- ciée à l’arc.
tentiels entre chaque paire de variables différentes Dans le cas de la contrainte élémentaire (une
avec des contraintes élémentaires d’égalité, et de contrainte d’égalité, différence, infériorité, etc.), les
forcer que la taille maximale de toutes les com- outils permettent déjà de fournir les explications né-
posantes connexes soit de 1. Dans ce cas, l’algo- cessaires [7]. Il suffit donc d’expliquer la propagation
rithme propageant la propriété qui doit être véri- qui s’effectue sur les propriétés de graphes pour pou-
fiée déduira directement que chaque arc doit être voir expliquer l’ensemble. Par exemple, dans le cas du
absent du graphe (sinon les composantes seraient all_different, la contrainte en elle-même (via la pro-
de taille supérieure à 1). Cela se traduit par le priété de graphe associée) permet directement de dé-
fait que pour chacun de ces arcs retirés il faut duire que chaque arc doit être à absent. Ainsi, il est
propager l’inverse d’une égalité, c’est-à-dire une possible d’expliquer l’état de chaque arc, juste avec
différence, ce qui garantit bien que toutes les va- la contrainte en elle-même. Donc le filtrage qui sera
riables doivent être différentes. Si au contraire, effectué par chaque contrainte élémentaire (des dif-
un arc était devenu présent de manière sûre, la férences ici), utilisera l’explication du domaine de la
contrainte élémentaire associée aurait été activée deuxième variable et l’explication de l’arc, c’est-à-dire
(au lieu de son opposée). la contrainte uniquement.
Pour résumer, ces cadres permettent de décrire Dans des cas plus compliqués (voir la figure 1), l’état
sémantiquement le filtrage que doit effectuer une d’un arc peut être modifié car le solveur déduit qu’une
contrainte, voire dans certains cas de dériver automa- contrainte élémentaire est forcément vérifiée. Ainsi,
tiquement l’algorithme de filtrage associé [1, 5]. Étant dans l’exemple de la figure 1, si on avait comme pro-
donnés ces résultats, il semble donc très intéressant priété de graphe que les composantes était au plus de
taille 2, il serait alors possible de déduire que tous les l’efficacité d’origine de l’outil).
autres arcs reliant ces deux variables à d’autres va- Nous commençons par proposer une description
riables doivent être absent du graphe final. Pour ex- brève de la programmation par aspects, ses notions
pliquer cet état, il suffit de justifier l’état de l’arc qui de base et une implémentation pour Java, AspectJ.
est forcément présent (ce qui est comme nous l’avons Nous en profitons pour présenter une application clas-
vu possible puisqu’il s’agit de contraintes élémentaires sique de cette technique que l’on peut appliquer pour
dont on sait expliquer le comportement), et d’ajouter la PPC, la génération de traces. Nous montrons en-
à l’explication la contrainte en cours qui a permis de suite comment l’appliquer à la génération d’explica-
modifier l’état de ces arcs (passage d’un arc potentiel tions pour la PPC, puis nous montrerons les résultats
à un arc absent du graphe). obtenus avec une première implémentation.
Outre la factorisation du code pour une multitude
de contraintes, l’avantage d’utiliser ce cadre basé sur
les propriétés de graphes pour générer des contraintes 5.1 La programmation par aspects
expliquées provient de la précision des explications que La programmation par aspects [9] est une technique
l’on peut générer. En effet, on voit bien dans le dernier de génie logiciel qui permet de factoriser du code que
exemple que seules les explications des domaines de l’on souhaite déployer en de nombreux endroits. Les
variables qui ont vraiment un rapport avec le filtrage deux principaux avantages de cette technique sont,
ont été prises en compte. pour la programmation par contraintes, d’une part de
simplifier l’étape de développement en proposant des
5 Utilisation des aspects outils simples pour éviter la duplication de code, et
d’autre part de fournir du contenu modulable. En ef-
Le principal défaut de la méthode intrusive était de fet les différents aspects peuvent être ou non ajoutés
devoir reprendre tous les algorithmes de filtrage un à au programme original, ce qui permet de brancher ou
un, en modifiant le code directement : il est nécessaire débrancher très facilement de nouvelles fonctionnali-
d’avoir accès au code (ce qui n’est pas toujours le cas), tés.
le solveur doit être modifié pour prendre en compte les La programmation par aspects (AOP) s’appuie au-
explications, et chaque contrainte doit être dupliquée, tour de trois notions particulières :
ce qui engendre bien entendu des problèmes de ver- – les join points (points de jonction) sont des points
sions, oublis de corrections d’erreurs, etc. L’avantage précis dans le déroulement d’un programme où
de la solution basée sur les cadres génériques de des- l’on souhaite ajouter du comportement,
cription de contraintes est qu’elle permet de factoriser – les pointcuts (coupes) représentent des ensembles
la difficulté à développer de telles contraintes. Ainsi de join points décrits à l’aide d’un langage dédié,
l’investissement de départ est plus lourd mais peut être – les advices (code advice) sont les fonctionnalités
amorti étant donné le nombre de contraintes que l’on que l’on souhaite ajouter.
peut générer à l’aide de ces cadres. Ainsi, pour utiliser l’AOP, il suffit de définir des
Cependant, le principal défaut d’un cadre générique point cuts pour décrire où l’on souhaite ajouter du
est souvent de perdre un peu d’efficacité (même si ce code, et les advices qui doivent contenir ce code fac-
n’est pas toujours le cas comme l’ont montré les tra- torisé. De plus, il peut être intéressant d’ajouter de
vaux de [1]). Nous proposons donc ici de trouver un in- l’information aux objets traités, sans devoir passer par
termédiaire entre ces deux solutions. En effet, moyen- le mécanisme d’héritage ou tout autre mécanisme pro-
nant la supposition que l’on ne souhaite pas résoudre posé par le langage. Pour cela l’AOP permet de faire
de problèmes dynamiques, on peut remarquer que gé- des modifications inter type, c’est-à-dire modifier la
nérer des explications ne consiste qu’à générer de l’in- structure même d’un objet (ajouter un champ, une
formation lors du déroulement de l’algorithme de fil- méthode, etc.). À l’aide de ces notions, l’AOP four-
trage à différents points du code. C’est typiquement ce nit des outils pour tisser ces nouvelles fonctionnalités
que permet d’effectuer la programmation par aspects avec le logiciel cible (sous forme de bytecode ou de code
qui consiste à ajouter du code en des points précis du compilé), c’est-à-dire que le code compilé est modifié
code original (ou du bytecode si l’on ne possède pas les pour prendre en compte ces ajouts.
sources mais l’API précise des contraintes et de l’al- L’application la plus évidente de l’AOP reste la gé-
gorithme de recherche) : il n’est donc plus nécessaire nération de trace. C’est d’ailleurs une des premières
de modifier le code lui-même (ou un clone) et permet applications qu’en avaient faite les auteurs pour implé-
donc de rendre l’ajout des explications complètement menter la trace GenTra4CP du projet OADymP-
modulaire (au même titre qu’un aspect de trace, les PAC[3] pour Choco [10]. En effet, générer de telles
explications peuvent être débranchées pour retrouver traces demande d’accéder à des informations qui ne
sont accessibles qu’au cœur du solveur (gestion des – pour chaque choix du branchement, la modifica-
événements, suivi de la propagation, etc.). Cependant, tion sur le domaine concerné doit être justifiée
sa génération reste coûteuse (tout comme pour les ex- avec une explication contenant une référence vers
plications, comme nous le verrons plus tard). Il est ce choix ;
donc important, d’une part d’avoir à modifier le code – à chaque retour arrière ajouter une explication
dans tout le solveur (chaque contrainte, chaque type au retrait du choix sur la variable que l’on vient
de branchement, chaque domaine de variables, etc.) et d’annuler, pour pouvoir construire incrémentale-
d’autre part de pouvoir débrancher facilement cette ment l’explication de l’absence de solution d’un
trace, pour ne pas perdre d’efficacité lorsqu’elle n’est problème ;
pas nécessaire. – modifier les domaines et variables pour prendre
Comme le montre la section suivante, ces problé- en compte les explications.
matiques sont très proches de celles de la génération Pour rendre l’exemple lisible, nous illustrons ici le
d’explications, ce qui explique que l’AOP soit aussi cas le plus simple, à savoir ajouter une explication au
intéressante dans ce cas. Nous illustrons nos propos niveau des choix du branchement. Pour cela, on crée un
ici avec AspectJ, car il s’agit d’un des outils les plus pointcut décrivant un tel choix, le but étant de réus-
connus pour l’AOP. Il ne s’agit cependant pas de l’outil sir à isoler l’endroit où se situe la prise de décision
le plus rapide ni le plus adapté à notre problème, mais lorqu’une variable est instanciée par l’algorithme de
semble suffisant pour illustrer nos propos. De plus, les branchement. On peut obtenir une telle coupe de la
exemples seront appliqués à Choco dont on a désac- manière suivante :
tivé la gestion des explications, pour réimplémenter à
partir de rien un système avec explications3 . pointcut assignVal(IntVar var) :
call(* IntVar+.setVal(*))
&& target(var)
5.2 Application aux explications && cflow (execution
(* AssignVar+.goDownBranch(..)));
La programmation par aspects peut être utilisée de
deux manières : soit il s’agit d’un outil de génie logiciel
Ce pointcut permet de décrire un point d’exécution
classique que l’on exploite dès la conception d’un outil
du programme ayant les caractéristiques suivantes :
principalement pour rendre l’outil modulaire ; soit il
– la méthode setVal est appelée sur une variable :
s’agit d’un outil permettant de faire évoluer/modifier
le call représente un appel à une méthode au-
un outil existant (les deux objectifs n’étant bien en-
quel on fournit une description de ce que peut
tendu pas à opposer). Dans un précédent article, il
être cette méthode (ici une méthode qui renvoie
a été montré comment les explications pouvaient être
n’importe quoi *, sur un objet de type IntVar
vues comme un aspect dans un solveur en partant d’un
ou une classe qui en hérite +, dont la méthode se
squelette de solveur. Ceci exposait bien le premier cas
nomme setVal et enfin qui prend n’importe quels
dont nous venons de parler, mais ne montrait pas qu’il
arguments) ;
était possible d’appliquer cela d’une part à des solveurs
– on unifie alors la variable en paramètre du point-
existants (ce qui est nécessaire pour pouvoir industria-
cut vers la variable modifiée (la cible target de
liser l’utilisation d’explication dans des solveurs com-
la méthode définie ci-dessus) ;
merciaux) et d’autre part dans des configurations plus
– cet appel doit se faire depuis l’exécution de la
complexes mettant en œuvre des contraintes globales.
méthode goDownBranch du branchement utilisé ;
Pour utiliser les explications avec la PPC et avec c’est ce que permet de vérifier l’instruction cflow :
les contraintes globales, il est nécessaire d’ajouter la pile d’appels des méthodes est utilisée pour
quelques informations et comportements dans le sol- vérifier que l’on exécute bien une méthode nom-
veur pour générer et maintenir les explications au long mée goDownBranch de la classe AssignVar ou une
de la recherche de sorte à exploiter un minimum l’in- classe dérivée de cette dernière.
formation à l’aide de l’algorithme mac-cbj [14]. Les Maintenant que l’on a décrit l’endoit où il convient
principales modifications à apporter sont les suivantes : d’ajouter de l’information, il faut maintenant dire pré-
– créer une classe d’objets contenant une expli- cisément ce qui doit y être ajouté, et si cela doit avoir
cation (CustomExplanation dans la suite des lieu, avant, après, à la place. . . dudit endroit. Pour
exemples) ; cela, on ajoute alors un advice :
3 On notera cependant qu’historiquement Choco n’a pas été
before(IntVar var) : assignVal(var) {
développé pour générer des explications, mais qu’il s’agit sim-
plement d’une intégration de Palm [7] pour rendre l’accès aux CustomExplanation exp =
explications plus simple new CustomExplanation(
 [Link]().getWorldIndex() - 1, 1. on cherche l’autre variable de la contrainte
[Link]()); otherVar (car c’est son domaine qui a déclenché
[Link]().explanation = exp; ce filtrage) ;
} 2. on génére une explication justifiant le do-
Comme on le voit, l’advice doit se dérouler avant maine de cette seconde variable et on lui
le pointcut (before), et doit construire une nouvelle ajoute la contrainte de différence elle-même
explication comprenant une information à propos du cst.self_explain(expl) ;
monde actuel, c’est-à-dire la taille de la pile de la re- 3. on fournit l’explication au domaine pour que ce
cherche. Cette explication est alors ajoutée dans les dernier puisse la prendre en compte lors de l’exé-
informations contenues dans les variables. Par souci de cution du filtrage (juste après cet advice par défi-
place, nous ne détaillerons pas toutes les modifications nition de celui-ci).
à apporter au solveur, mais il est intéressant de remar- Dans le cas d’une contrainte globale, exactement le
quer qu’au final, moins de 200 lignes sont ainsi néces- même mécanisme devra être mis en place. La diffé-
saires pour instrumenter Choco avec des fonctionnali- rence vient surtout du fait que les algorithmes sont
tés de base sur les explications. plus compliqués, exploitent des structures de données,
Nous nous intéressons maintenant aux contraintes, et qu’il est donc nécessaire d’en tenir compte pour gé-
le cœur du sujet. Comme nous l’avons vu dans la pre- nérer les explications. Dans un souci de clarté, nous
mière solution pour implémenter des contraintes glo- considérons ici une contrainte simple d’occurrence. Le
bales, ajouter des explications demandent deux types but est d’assurer qu’à tout moment, le nombre d’oc-
de modifications : générer les explications au fur et currences d’une valeur fixe donnée λ dans un ensemble
à mesure du filtrage, et maintenir les structures de de variables v1 , v2 , . . . vn est compris entre la borne in-
données dans le cas du dynamique. Seul le premier férieure et supérieure d’une variable d’occurrence occ
problème nous intéresse ici puisque nous avons fait (il s’agit en fait d’un cas très simple d’application de
l’hypothèse que les problèmes traités ne seront pas la contrainte de cardinalité bien connue). Pour filtrer
dynamiques (ou bien seront traités comme plusieurs efficacement, cette contrainte maintient incrémentale-
résolutions statiques consécutives). ment le nombre de variable pouvant prendre la valeur
Tout d’abord commençons par une contrainte ba- fixée λ et le nombre de variables instanciées à cette
sique et très simple : la différence entre deux variables. valeur. Dès lors, les deux règles suivantes sont appli-
On voit alors très bien, que dès lors qu’aucune struc- qués :
ture de données n’est utilisée, il est très simple d’ins- – si le nombre de variables pouvant être instanciées
trumenter une contrainte avec des explications. En ef- à λ est égal à la borne inférieure de occ, alors
fet l’algorithme trivial de cette contrainte est de vé- toutes ces variables doivent être instanciées ;
rifier, à chaque fois que cela peut arriver, si l’une – si le nombre de variables devant être instanciées
des variables est instanciée, et dans ce cas retirer la à λ est égal à la borne supérieure de occ, alors
valeur de cette variable du domaine de l’autre va- toutes les autres variables ne doivent pas être ins-
riable. Donc si l’on suppose que l’on possède un point- tanciées à cette valeur et donc λ est retiré de leurs
cut neqXYCAnyFiltering qui référence l’ensemble des domaines.
points où un tel filtrage peut avoir lieu, on peut lui Pour expliquer ce comportement, il faut donc :
associer l’advice suivant : – à chaque fois que le nombre de variables instan-
ciées ou pouvant être instanciées à λ est modifié,
before(NotEqualXYC cst, IntVar var) :
stocker l’explication ou tout au moins un moyen
neqXYCAnyFiltering(cst, var) {
de retrouver l’explication de cette nouvelle valeur
IntVar otherVar = [Link](0);
(maintenir la liste des variables qui permettent de
if (otherVar == var)
justifier ce nombre suffit),
otherVar = [Link](1);
– à chaque fois qu’une règle de filtrage est appelée, il
CustomExplanation expl = new
faut que l’advice utilise ces explications stockées,
CustomExplanation([Link]());
y ajoute la contrainte en cours, et informe le do-
cst.self_explain(expl);
maine filtré que cette explication justifie le retrait
otherVar.self_explain(
de la ou des valeurs en question.
[Link], expl);
Prendre en compte des contraintes plus compliquées
[Link]().explanation = expl;
comme le all_different ou le flow n’apporte pas
}
plus de difficulté. La seule limitation qu’il peut y avoir
Ainsi, on voit que la génération de l’explication se provient de l’accès à certaines données qui ne sont pas
déroule en trois temps : publiques. Dans ce cas, une solution revient à hériter
 Problème Sans expl. Expl. intrus. AOP bale, qui comprend notamment des structures de don-
Diff.(14) 0.19s 0.62s 0.78s nées à maintenir et utiliser pour générer les explica-
Diff.(16) 0.77s 1.4s 1.8s tions comme nous l’avons vu dans la section précé-
Diff.(18) 6.1s 12.1s 15s dente, nous proposons de résoudre un problème sur-
Occur.(14) 12.1s 8.1s 9.6s contraint illustratif avec des contraintes d’occurrence.
Pour cela, considérons un problème avec n variables.
Tab. 1 – Résultats des premières expérimentations Les n − 1 premières ont un domaine allant de 1 à 5 et
(avec entre parenthèse la taille n du problème) sur un la dernière a un domaine qui vaut [[5, 6]]. On ajoute en-
Celeron 900 MHz et les options par défaut de compi- suite des contraintes d’occurrence sur l’ensemble de ces
lation Java contraintes pour assurer que la valeur 3 apparaı̂t n/2
fois, que la valeur 4 apparaı̂t exactement n/2 fois aussi
de la contrainte, ajouter des accesseurs aux données et la valeur 6 une fois (en fait cette dernière contrainte
dont on a besoin dans l’aspect et de modifier le com- et la dernière variable ne font qu’ajouter du bruit pour
portement du constructeur pour renvoyer une instance tester l’explication retournée). Encore une fois, il est
de la nouvelle classe au lieu de l’ancienne. trivial de voir que le problème est sur-contraint. Si
on lance la résolution avec les explications, on obtient
bien une explication contenant les deux premières oc-
5.3 Évaluation currences qui sont bien inconsistantes.
Les expérimentations permettent d’obtenir les ré-
Pour apporter une première évaluation de l’utilisa-
sultats reportés dans le tableau 1. Comme on peut
tion de l’AOP pour générer des explications à la volée
le voir, l’exploitation des explications a même per-
durant la résolution d’un problème de satisfaction de
mis d’améliorer le temps nécessaire pour déterminer
contraintes, nous proposons ici dans un premier temps
le fait que le problème est sur-contraint grâce au gain
de tenter de résoudre un problème surcontraint com-
que l’on peut tirer de mac-cbj (même s’il s’agit d’un
prenant uniquement des contraintes basiques de diffé-
phénomène qui ne se généralise malheureusement pas
rence. En effet, utiliser de telles contraintes à la place
souvent, cela montre bien que la génération des expli-
de contraintes globales, permet d’augmenter artificiel-
cations peut être amortie par l’exploitation de cette
lement la phase de propagation et ainsi d’évaluer de
information durant la recherche en évitant d’explorer
manière pessimiste le coût que pourrait avoir l’utilisa-
des régions de l’espace de recherche vouées à l’échec).
tion des explications.
Il ne s’agit ici que de tests préliminaires, une cam-
Ainsi, nous tentons de résoudre un problème avec n
pagne de tests étant en cours de réalisation pour tester
variables, et avec une clique de différence entre les n/2
ces résultats sur des problèmes plus réalistes. Cepen-
premières variables (ce qui signifie que chaque variable
dant ces premiers résultats montrent bien d’une part
doit avoir une valeur différente de celles de toutes les
que la proposition d’utiliser les aspects fonctionne bien
autres du même ensemble comme pour la contrainte
(il est possible de modifier un solveur déjà existant sans
all_different), et pour les n/2 dernières variables.
modifier son code de manière intrusive, en ce sens il
De plus, une contrainte lie une variable de la première
s’agit déjà d’un test réaliste) et que son surcoût par
clique avec la deuxième clique. Enfin, chacune des va-
rapport à une méthode classique est minime.
riables contient les mêmes n/2−1 valeurs. Le problème
est donc trivialement sur-contraint.
Si on lance la résolution sans explication, avec des 6 Comparaisons des techniques et conclu-
explications implémentées de manière intrusive, et en- sion
fin à l’aide d’aspects, on obtient les résultats reportés
dans le tableau 1. On remarque d’une part que le coût Nous avons présenté dans ce papier les difficultés que
de la gestion des explications est acceptable (environ peut poser l’ajout d’une nouvelle fonctionnalité comme
deux fois plus de temps dès que le problème devient les explications dans un solveur de contraintes. Outre
suffisamment compliqué) mais aussi et surtout que la la solution classique qui consiste à implémenter la nou-
version traitée avec les aspects est relativement effi- velle fonctionnalité dans tout le solveur, nous propo-
cace, le surcoût par rapport à la version intrusive étant sons deux nouvelles méthodes pour tenter de réduire
largement acceptable. De plus, bien entendu, le solveur le coût d’un tel développement. Ainsi, le tableau 2 ré-
ne se limite plus à répondre uniquement qu’il n’y a sume les avantages de chaque proposition, depuis l’uti-
pas de solutions, mais précise aussi qu’une explication lisation de cadres génériques qui peut demander un
peut être constituée d’une seule des deux cliques de temps de développement conséquent au début mais
différences, ce qui est bien le comportement souhaité. fournit ensuite à moindre coût un très grand nombre
Afin de tester la solution sur une contrainte glo- de contraintes avec la fonctionnalité souhaitée (que ce
 Méthode ad hoc Cadres génériques AOP
Investissement initial faible fort moyen
Développement pour chaque contrainte fort faible moyen
Efficacité fort moyen assez fort
Problèmes dynamiques gérés gérés non gérés

Tab. 2 – Avantages et inconvénients des différentes méthodes

soit les explications ou la génération de trace) si l’on [5] Dávid Hanák. Implementing global constraints as graphs
accepte de perdre une partie de la complétude du fil- of elementary constraints. Acta Cybern., 16(2) :241–258,
2003.
trage sur certaines contraintes ; jusqu’à l’utilisation de
[6] Ulrich Junker. QUICKXPLAIN : Conflict detection
la programmation par aspects qui permet d’ajouter ou for arbitrary constraint propagation algorithms. In IJ-
de modifier le code d’un logiciel de manière non intru- CAI’01 Workshop on Modelling and Solving problems with
sive en définissant des coupes où l’on souhaite ajouter constraints, Seattle, WA, USA, August 2001.
un nouveau code (en effet, cette méthode ne nécessite [7] Narendra Jussien and Vincent Barichard. The PaLM
pas de modifier le code originel ni de réduire l’efficacité system : explanation-based constraint programming. In
TRICS a post-conference workshop of CP’00, pages 118–
du solveur lorsque l’on utilise pas les explications). 133, September 2000.
Comme nous l’avons vu cette dernière technique [8] Narendra Jussien, Romuald Debruyne, and Patrice Boizu-
peut se révéler très efficace puisque le surcoût est mi- mault. Maintaining arc-consistency within dynamic back-
nime. La principale limitation actuellement est cer- tracking. In CP’00, number 1894 in LNCS, pages 249–261,
tainement la connaissance intime nécessaire du sol- 2000.
veur. Nous travaillons actuellement au développement [9] Gregor Kiczales, John Lamping, Anurag Menhdhekar,
Chris Maeda, Cristina Lopes, Jean-Marc Loingtier, and
d’un langage d’aspects pour la programmation par John Irwin. Aspect-oriented programming. In Procee-
contraintes indépendant du solveur utilisé manipulant dings European Conference on Object-Oriented Program-
des concepts haut niveau spécifiques à la program- ming, pages 220–242, 1997.
mation par contraintes (à l’image de ce qui a été [10] François Laburthe. Choco : implementing a cp kernel.
fait pour la trace trace GenTra4CP du projet OA- In TRICS, a post-conference workshop of CP 2000, 2000.
Site : [Link].
DymPPAC[3].
[11] Ludovic Langevine. Explication systématique des
Dans de futurs travaux, il semble intéressant d’im- contraintes indexicales. In JFPC’05, Lens, France, May
plémenter la deuxième proposition basée sur les cadres 2005.
génériques pour pouvoir évaluer de manière pratique [12] Gilles Pesant. A filtering algorithm for the stretch
d’une part son efficacité en terme de temps de cal- constraint. In Principles and Practice of CP (CP 2001),
cul mais aussi en terme de qualité d’explications géné- LNCS, pages 183–195, 2001.
rées. En effet, cette solution semble très intéressante [13] Gilles Pesant. A regular language membership constraint
for finite sequences of variables. In CP’04, pages 482–495,
dans le sens où elle répond à un deuxième problème 2004.
de la programmation par contraintes, à savoir le coût [14] Patrick Prosser. Hybrid algorithms for the constraint sa-
de développement des contraintes globales qui entraı̂ne tisfaction problem. Computational Intelligence, 9(3) :268–
souvent la présence d’un nombre limité de contraintes 299, August 1993.
dans les solveurs académiques. [15] Jean-Charles Régin. A filtering algorithm for constraints
of difference in CSPs. In AAAI ’94, pages 362–367, 1994.

Références [16] Jean-Charles Régin. Generalized arc consistency for global

cardinality constraint. In AAAI/IAAI, Vol. 1, pages 209–
[1] Nicolas Beldiceanu, Mats Carlsson, and Thierry Petit. 215, 1996.
Deriving filtering algorithms from constraint checkers. [17] Guillaume Rochart and Narendra Jussien. Une contrainte
In Principles and Practice of Constraint Programming stretch expliquée. JEDAI : Journal Électronique d’Intel-
(CP’04), pages 107–122, 2004. ligence Artificielle, 3(31), 2004.
[2] Romuald Debruyne, Gérard Ferrand, Narendra Jussien,
Willy Lesaint, Samir Ouis, and Alexandre Tessier. Correct-
ness of constraint retraction algorithms. In FLAIRS’03,
pages 172–176, St. Augustine, Florida, USA, 2003.
[3] Pierre Deransart. Projet OADymPPAC, 2004. Site :
[Link]/OADymPPaC/.
[4] Étienne Gaudin, Narendra Jussien, and Guillaume Ro-
chart. Implementing explained global constraints. In CP04
Workshop on Constraint Propagation and Implementation
(CPAI’04), pages 61–76, 2004.