Spécialisation du système de maintien de d’éduction

Solution pour une hiérarchie

Une H-solution, pour un problème et une hiérarchie donnes, est une instanciation de chacune des variables apparaissant dans les contraintes de la hiérarchie. Une telle solution respecte plus ou moins les contraintes du problème. Notons que dans les travaux de Wilson et Borning[1993],ne sont considérées que lesH-solutions veriant les contraintes requises.
Il existe differentes fa cons d’apprecier la verication d’une contrainte. On peut prendre une approche simple (c’est celle que nous conserverons tout au long de ce travail) et dire qu’une contrainte est veriée ou qu’elle ne l’est pas. On peut aussi définir une notion de distance entre l’etat courant des domaines des variables et l’idéalité que représente la verication de la contrainte permettant ainsi de formaliser une notion de contrainte plus ou moins variée.

Préférences et Interactivité

Il n’est pas toujours possible de connaître a priori toutes les préférences que l’utilisateur accorde aux contraintes du problème. En effet, il peut y avoir un très grand nombre de contraintes ou bien une préférence peut de pendre totalement du contexte de résolution. La préférence accordée a une contrainte peut ainsi être modifie au cours du temps.
C’est pourquoi, un système interactif , ne faisant appel a l’utilisateur qu’en cas de nécessité, a son inter^et. Ainsi, il serait possible de demander a l’utilisateur de définir ses préférences sur de petits sous-ensembles de contraintes ce qui parait plus raisonnable que de toutes les demander avant de démarrer la résolution ou a chaque fois qu’une nouvelle contrainte est introduite.

Maintien d’arc-consistance

Les algorithmes dnac4 [ Bessiere, 1991] et dnac6[Debruyne, 1995] sont des extensions des algorithmes classiques d’arc-consistance ac4[ Mohr et Henderson, 1986]etac6[ Bessiere et Cordier, 1993; Bessiere, 1994]qui permettent degerer des systemes dynamiques de contraintes.
Pour mener a bien un retrait efficace de contraintes, ces deux algorithmes enregistrent des informations au fur et mesure de la résolution pour connaitre les effets d’une contrainte. Ils utilisent la notion de justication la contrainte qui a un moment donne est responsable du retrait d’une valeur dans le domaine d’une variable.
Ces informations sont alors utilisées pour déterminer quels sont les retraits de valeur qui dépendent directement ou indirectement (par propagation) de la contrainte retirée. Ensuite, de tels retraits étant susceptibles d’^etre realises (justies) d’une autre manière, il faut rétablir la cohérence.
Citons l’algorithmeacjdcpropose par Neveu et Berlandier[1994] qui n’utilise pas de système d’enregistrementetdoncnetravaille que sur les contraintes du probleme. Cette approche a ete proposee pour reduire la complexité des autres algorithmes (dnac4etdnac6). En fait, ce gain en espace se paye par une complexité en temps sensiblement augmentée.
Le tableau 3.1 donne les complexités spatiales et temporelles de ces trois algorithmes (nvariables de domaine de taille maximum lesquelles portent e contraintes). On trouve une comparaison experimentale de ces trois approches dans [Debruyne, 1995].

Relaxationdecontraintes sur les problemes dynamiques

Dans cette section, nous nous interessons aux travaux lies aux ajouts/retraits de contraintes dans les systemes dynamiques de contraintes.
Le systemeihcs (Incremental Hierarchical ConstraintSolver) proposeparMenezes[Menezeset al., 1993; Menezes et Barahona, 1996 ] a pour but de fournir des solveurs de hierarchie incrementaux en vue d’une utilisation dans le cadre hclp.
En fait, il ne s’agit plus vraiment d’un systemehclppuisque seuls les concepts de base sont utilises et que la vision operationnelle proposee par Borning n’est pas respectee.
L’approche proposee parihcs est une technique d’exploration d’un espace de congurations. Une conguration est un triplet hASRSUSi de contraintes actives (AS), relaxees (RS)eta traiter (US). Les contraintes ne sont pas alors traitees forcement selon leur ordre d’arrivee dans le systeme. Le choix d’une contrainte aintegrer depuis l’ensembleUSest laisse au libre choix de l’implanteur.
An, de limiter l’exploration de l’espace de recherche a une petite partie, Menezeset al.utilisent la notion de dependance entrecontraintes.

Definition Dependance entre contraintes

Une contraintec adepend d’une contraintec b si et seulementsic b a retireunevaleur dans le domaine d’une variable qui apparat dans c a.
Lorsqu’une contradiction est identiee, c’est qu’au moins une contrainte n’est plus veriee. Ainsi, on peut limiter la recherche d’une conguration optimale aux congurations denies a partir des contraintes dontdepend la contrainte en echec.
Plus precisement, un ordre total est deni sur les congurations determinees a partir du sous-ensemble des contraintes du probleme dontdepend la contrainte en echec. Ensuite, la recherche est realisee suivant cet ordre jusqu’ a ce que soit trouvee une conguration satisfaisante.
Le changement de conguration est en fait realise par backtrack standard. Tout ce qui a ete calculeentre l’instant d’introduction de la contrainte relaxee et l’instant de sa relaxation est completement remis en cause. Il n’evite donc pas le phenomene dethrashingpendant le traitement d’un retrait de contrainte.
Cette approche, bien que nommee incrementale, ne l’est pas totalement. Pour les retraits de contraintes, on ne retrouve pas l’incrementalite que l’on a pour l’ajout.
En eet, le retrait est realise par backtrack sans tenir compte de ce qui s’est passe entre l’introduction de la contrainte a relaxer et l’instant de sa relaxation.
De plus, on peut d’ores et déjà constater que la notion de dépendance entre contraintes pourrait ^ être rendue plus précise permettant ainsi de circonscrire la recherche a un plus petit ensemble de configurations. On peut en effet préférer travailler sur les valeurs des variables permettant alors de précisément les liens entre les contraintes et les variables.
Neanmoins, signalons les travaux recents de Holzbauret al.[1996]qui proposent une adaptation efficace (nous proposons quelque chose de tres similaire chapitre 5) de la philosophieihcs au cas des contraintes lineaires sur les rationnels.

Propagation locale

Si on se limite aux contraintes ditesfonctionnel les, on peut appliquer des techniques de propagation locale[Trombettoni, 1997]. Les modications sur les valeurs des variables sont alors propagees simplement en utilisantlesmethodes.
L’utilisation de telles techniques permet alors de proposer des systemes incrementaux capables de resoudre des problemes sur-contraints dans le cadre d’hclp.
Ainsi, l’algorithme DeltaBlue[Freeman-Benson et al., 1990 ] permet de traiter par propagation locale des systemes de contraintes fonctionnelles simples (variable de sortie unique) dont le graphe de dependance est sans circuit. Depuis, une extension a ete proposee : l’algorithme SkyBlue[Sannella, 1993]qui permet de traiter les contraintes fonctionnelles a sorties multiples et dont le graphe de dependance contient des circuits. Ces deux algorithmes sontconcus pour fonctionner avec le comparateurCLPB.
Le systeme Houria [Bouzoubaaet al., 1995 ] permet de calculer une solution respectant d’autres comparateurs. Par contre, le systeme de contraintes resolu doit etre sans circuit.
L’utilisation de la propagation locale pour des contraintes non fonctionnelles a conduit au systeme Indigo[Borninget al., 1996 ]. Ce systeme permet de traiter des contraintes d’inegalite(x6y) en utilisant une sorte de propagation d’intervalles.
Malheureusement, les auteurs signalent qu’ils n’ont pu proposer une version incrementale de cet algorithme. Ceci est d^ u au fait que jusqu’a maintenant il n’existe pas de proposition de systeme incremental sur les intervalles dans la litterature. Citons enfin les travaux theoriques presentes dans[Haselbocket al., 1993 ] qui proposent un cadre formel pour les techniques de réparation de solution dans le cas d’une solution ne respectant pas l’ensemble des contraintes d’un problème.

Dynamic Backtracking et la relaxation de contraintes

L’algorithmeDynamic Backtrackingfonctionne comme un veritable systeme de relaxation de contraintes sur des contraintes speciques : les contraintes d’aectation de valeur a une variable. En effet, considerons l’aectation d’une valeur a une variable comme un ajout de contrainte d’egaliteetdem^eme, la desaectation comme un retrait (une relaxation) de cette meme contrainte. Ainsi, lorsque l’aectation partielle est incoherente c’est que le systeme de contraintes courant est inconsistant ; l’algorithme determine alors lameil leure(plus utile) contrainte (d’egalite) a relaxer (desaectation) sans modier l’etat des autres contraintes (aucune modication des autres aectations). Ceci etantrepete jusqu’ a ce qu’une aectation partielle coherente soit trouvee pour pouvoir continuer. On peut recapituler les caracteristiques de ces trois algorithmes dans un tableau (cf.tableau 3.2) presentant leur comportement par rapport a l’identication d’un pointdechoix pertinenta remettre en cause, la capaciteaeviter lethrashinget l’utilisation d’un dms.

Table des matières

1 Introduction 
1.1 Contexte du travail
1.2 Problematique
1.3 Notre these
1.4 Contributions et organisation de la thèse
I Contexte de l’étude
2 Définitions 
2.1 Problemes de Satisfaction de Contraintes
2.1.1 Systeme de contraintes
2.1.2 Satisfaisabilite d’un systeme de contraintes
2.1.3 Instances du schema general
2.2 Systemes dynamiques de contraintes
2.2.1 Problemes dynamiques
2.2.2 Systemes reactifs
2.2.3 Problemes sur-contraints
2.3 Prise en compte de preferences
2.3.1 Preference et hierarchie
2.3.2 Solution pour une hierarchie
2.3.3 Preferences et Interactivite
2.4 Resolution d’un systeme de contraintes sur-contraint
2.4.1 Configuration et propriet le maintenue
2.4.2 Comparateurs
2.4.3 Solution pour un probleme sur-contraint
2.5 Le cadre du travail : un systeme de relaxation de contraintes
3 Etat de l’art 
3.1 Systemes de Maintien de Deduction
3.2 ((Apprentissage))pour les problemes dynamiques
3.2.1 Une premiere approche : les oracles
3.2.2 Maintien d’arc-consistance
3.2.3 Diagnostic d’echec
3.2.4 plcreactive sur les domainesnis
3.3 Relaxation de contraintes sur les problemes statiques
3.3.1 Hierarchical Constraint Logic Programming
3.3.2 Partial Constraint Satisfaction Problems
3.3.3 Cadres generaux pour la relaxation
3.3.4 Autres approches
3.4 Relaxation de contraintes sur les problemes dynamiques
3.4.1 Instance((incrementale))dehclp: le systemeihcs
3.4.2 Propagationlocale
3.4.3 ((Precurseurs))de la relaxation de contraintes
3.5 Motivations
II Un cadre general pour la relaxation 
4 Un cadre general : relax(D, C, P) 
4.1 L’espace de recherche
4.2 Une approche de type meilleur d’abord
4.2.1 Un exemple
4.2.2 Notions de base
4.2.3 Algorithme de recherche deC-solution
4.3 Semantique operationnelle demaj-configuration
4.3.1 Mise a jour de la configuration courante
4.3.2 Modication de l’arbre de recherche
4.3.3 Conclusion
4.4 Specication demeilleure-configuration
4.4.1 Le probleme de recouvrement
4.4.2 Utilisation d’un comparateur quelconque
4.4.3 Les comparateurs contradiction-local
4.5 Conclusion
5 Systemes lineaires sur les rationnels : relax(Q,Lin,Psol) 
5.1 Presentation
5.1.1 Denitions
5.1.2 Realisabilite d’un systeme lineaire
5.1.3 Verification dePsol
5.2 Instance du schema general de relaxation
5.2.1 Fournir une explication de contradiction
5.2.2 Exectuer la mise a jour de configuration
5.3 Conclusion
6 Maintien de d’eduction pour la reduction de domaine 
6.1 Techniques de resolution par reduction de domaines
6.1.1 Presentation
6.1.2 Un algorithme de reduction
6.2 Maintien de deduction pour la reduction
6.2.1 Conceptsdebase
6.2.2 Conditions fondamentales de bon fonctionnement
6.2.3 Simplication
6.2.4 Extensions de la notion de d eduction
6.3 Integration du Maintien de d eduction dans la recherche
6.3.1 Fournir des explications
6.3.2 Specication deexplique-contradiction
6.3.3 Specication demaj-configuration
6.4 Discussion
6.5 Conclusion
7 Instance sur les CSP : relax(FD,C,Pac) 
7.1 Le cadre general descsp
7.2 Specialisation de l’algorithme de eduction
7.2.1 Fonction d’approximation pour uncsp
7.2.2 Derents algorithmes d’arc-consistance
7.2.3 Specialisation des fonctions parametres
7.3 Enumeration sur lescsp:lacontrainteone-of
7.3.1 Integration de la phase d’enumeration
7.3.2 Modications pour le traitement de l’enumeration
7.3.3 Proprietes de la solution proposee
7.4 Complexie
7.4.1 Donnees de base
7.4.2 Complexie spatiale
7.4.3 Complexit etemporelle
7.4.4 Recapitulation
7.5 Discussion
7.6 Exemple complet : la conference
7.6.1 Enonceetmod elisation du probleme
7.6.2 Resolution
7.7 Conclusion
8 Instance sur les intervalles : relax(Interval,C,Pbc) 
8.1 Le cadre general descspnumeriques
8.1.1 Presentation
8.1.2 Reelsetdomainesnis
8.2 Specialisation de l’algorithmeder eduction
8.2.1 Consistance aux bornes
8.2.2 Fonction d’approximation pour un CSP numerique
8.3 Spécialisation du système de maintien de d’eduction
8.3.1 Simplication du systeme d’enregistrement
8.3.2 Modications induites
8.3.3 Le cas des contraintesdisjonctives
8.3.4Enumeration pour les intervalles
8.4 Complexite
8.5 Conclusion
9 Implementation pour les CSP 
9.1 Architecture generale
9.1.1 Schéma de fonctionnement
9.1.2 Composants
9.2 Implementation en claire
9.2.1 Le langage et ses specicites
9.2.2 Les variables
9.2.3 Les contraintes
9.2.4 Adaptation de l’approche
9.3 Conclusion
III Experimentations et Premieres Applications 
10 Experimentations 
10.1 Generation decspaleatoires
10.2 Conservation de la transition de phase
10.2.1 Protocole experimental
10.2.2 Premiers resultats
10.3 Etude sur des problemes dynamiques
10.4 Resolution de problemes de grande taille
10.5 Comparaison avec l’algorithmemac
10.5.1 Problemes aleatoires etdecorum
10.5.2 Problemes structures etdecorum
10.6 Conclusion
11 Traitement de la disjonction et contrainteone-of 
11.1 Traitements de la disjonction
11.2 Notre proposition
11.3Etude sur un probleme purement disjonctif
11.3.1 Le probleme d’Open-Shop
11.3.2 Premiers resultats
11.3.3 Resolution de problemes plus faciles
11.4 Conclusions
IV Conclusion
12 Conclusion et perspectives
12.1 Extensions de notre approche
12.2 Applications de décorum
12.3 Applications de la contrainteone-of
12.4 Interactivite
Références bibliographiques 
Liste des dentitions 
Liste des théorèmes 
Liste des algorithmes
Liste des exemples 
Table des grues 
Liste des tableaux 
Index

Lire le rapport complet