Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 1
Le concept de contraintes :propagation, satisfaction, programmation
Pierre LopezLAAS, Toulouse
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2
Préambule
n Présentation des concepts de base liés au raisonnementbasé sur les contraintes pour les problèmes de décision
n Définition et distinction des termes– propagation de contraintes– satisfaction de contraintes– programmation par contraintes
n Exposé introductif aux exposés suivants plusdirectement concernés par une utilisation pratique
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 3
Cadre : problèmes d'optimisation combinatoire
n Problème d'Optimisation Combinatoire = POC– critère(s) à optimiser– sous des contraintes, nombreuses, diverses
n Exemples industriels– gestion de projet– problèmes de tournées– confection d'emplois du temps– organisation du travail dans un atelier de fabrication– optimisation de réseaux (informatique, télécoms, spatial…)– problèmes de configuration, de conception…
n Complexité élevée (NP-difficiles)
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 4
Résolution d'un POC : méthodes exactes
n Programmation mathématique– programmation dynamique– programmation linéaire, en nombres entiers, en variables mixtes
n Procédures d'exploration arborescentesstratégies de parcours :– meilleur d'abord (BFBB)– profondeur d'abord et retour arrière chronologique (DFBB)– déviation limitée par rapport à une heuristique (LDS)
n Résultats spécifiques– propres à chaque type de problème
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 5
Résolution d'un POC : méthodes approchées
n Heuristiques– "procédure exploitant au mieux la structure du problème considéré,
dans le but de trouver une solution de qualité raisonnable en untemps de calcul aussi faible que possible"
– règles de priorité
n Métaheuristiques– cadre général de résolution
n exploration : permet de visiter des régions différentes dans l'espacedes solutions
n exploitation : permet de savoir où se trouvent les meilleures solutions
– à solution uniquen méthodes constructives : algorithmes gloutons, myopesn méthodes de recherche locale : Tabou, recuit simulé
– à population de solutionsn méthodes évolutives : algorithmes génétiques, colonies de fourmis
6
et la programmation par contraintes...
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 7
Paradigme dela programmation par contraintes (1)
n Séparation nette entre
– la description du problème en termes de variables et decontraintes à satisfaire
– un processus de déduction logique agissant sur lescontraintes
– les algorithmes pour résoudre le problème (processusd'instanciation des variables)
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 8
Paradigme dela programmation par contraintes (2)
n Un POC = < {variables}, {contraintes}, [critères] >
– une contrainte est une expression logique reliant des variables dedécision, chacune d'elle prenant ses valeurs dans un domaineexemples : x < y ; A ≠ B ; Z ∈ {blanc, noir} ; α + β + γ = 180
– une contrainte provoque une restriction sur les valeurs quepeuvent prendre simultanément les variables
– une solution est un ensemble d'instanciations (un n-uplet devaleurs)…
n … qui satisfait toutes les contraintes… (valides et cohérentesou consistantes)
n … et qui réalise l'extremum des critères éventuels (optimales)
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 9
Les CSP
n Un POC peut être défini comme une instance d'unproblème de satisfaction de contraintes
n CSP = (X,D,C)– X ensemble de variables– D domaines finis d'appartenance des valeurs des variables– C contraintes reliant les variables d'une certaine arité
n Le critère est intégré en tant que variable contrainte
critère < valeur_de_la_meilleure_solution
Ô recommencer la résolutionÔ si une inconsistance apparaît, la dernière solution
trouvée est l'optimale
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 10
POC, CSP : exemple en ordonnancement
n variables de décision (X)– dates de début– relations de succession entre tâches
n domaines (D)– définis par les dates limites (dates de disponibilité, dates échues)
n contraintes (C)– gammes
travail j : j1 → j2, (j1,j2)∈Oj et j2 successeur de j1– distances min/max entre tâches– ressources à capacité limitée (disjonctives/cumulatives)
machine i: a ↔ b, (a,b)∈Oi
n critères– minimisation de la durée totale de l'ordonnancement– minimisation du nombre pondéré de travaux en retard– minimisation du retard maximum…
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 11
Questions associées à un CSP
n Prouver la consistance d'un CSP (satisfiabilité) est unproblème NP-complet
n Exhiber une solution – admissible ou optimale – duCSP (satisfaction) est NP-difficile dans le cas général
– résolution : recherche arborescente en profondeur d'abordn generate and test : vérification du viol d'une contrainte après
instanciation de toutes les variables du problème (instanciationcomplète)
CSP de n variables, domaines de cardinal d, m contraintes :dn états terminaux, évaluation de mdn contraintes
n test and generate (algorithme backtrack) : vérification du viol d'unecontrainte après instanciation de toutes les variables inhérentes à lacontrainte
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 12
Algorithme Backtrack
n Inconvénient majeur : complexité exponentielle– découverte redondante d'inconsistances locales– non prise en compte d'informations triviales sur l'inconsistance
d'instanciations partielles
n Amélioration de l'algorithme– définition d'heuristiques sur l'ordre d'instanciation des variables
(first-fail, most-constrained, smallest...), des valeurs, descontraintes
– réduction de l'espace de recherche (par propriétés de consistancelocale ou procédures de filtrage ou techniques de propagation decontraintes) avant la recherche d'une solution
– modification de l'algorithme lui-même en tentant de détecter, àmoindre coût et le plus rapidement possible, l'inconsistance del'instanciation courante
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 13
Approches pour modifier Backtrack
– schémas rétrospectifs : backtrack intelligent(backjumping) ou nogood recording (mémorisation d'unensemble d'instanciations ne participant à aucunesolution)
+ schémas prospectifs (look-ahead schemes) : tirent partides filtrages – notamment la consistance d'arc – en lesutilisant dans la recherche
n forward checking (FC) : 1980n maintaining arc-consistency (MAC) : 1994
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 14
Schémas rétrospectif et prospectifdans Backtrack
backward checking
Instanciation courante
variable instanciée
variable non instanciée
forward checking partial look future full look future(MAC)
rétrospectif
prospectif
ordr
e d'
inst
anci
atio
n
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 15
Propagation de contraintes
n ensemble de techniques de ré-écriture permettant
n déduction de nouvellescontraintes
– la détection d'une inconsistance globale
x ≠ zx z
y
x = y y ≠ z
d'(x2)
x1
x2
d(x1)
d(x2)
d'(x1)
n réduction de domaines
– la vérification de la validité d'une solution– un renforcement de consistance par suppression (filtrage) des valeurs des
variables n'appartenant à aucune solution
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 16
Exemple de propagation
n CSP initial
Dx= Dy= Dz= Dw={1,2,3,4,5}
C1: x + 3 ≤ yC2: z = 2 * xC3: w = x * y
n Propagation 1 2 4 51 2 3 4 51 2 3 4 5
1 2 4 5 2 41 2 3 4 5
1 4 5 2 4 4 5
1 4 5 2 4 5
C2
C3
C2
x →y →z →w →
1 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 5
C1
unecontrainte est
nondirectionnelle
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 17
Consistance d'arc
Algorithme AC-3L ← {(i,j) | ∃Cij ∈ C}tant que L ≠ ∅
retirer une paire (k,m) de Lsi Revise(k,m)
L ← L ∪ {(i,k) | ∃ Cik ∈ C, i ≠ k, i ≠ m}
n Contexte : CSP binaireP=(X,D,C) où X={x}, D={Dx}, C={Cxx'}
Revise(i,j) : Booléenmodif ← fauxpour v ∈ Di
si O v' ∈ Dj tq {i ← v, j ← v'} consistantDi ← Di – {v}modif ← vrai
retourner modif
n Consistanced'arc =suppression devaleurs quirendentimpossible lasatisfaction detoute contrainteportant sur uncouple devariables
O(md3)[O(md2) pour AC-4]
18
le temps et les ressources...
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 19
Exemple de propagation en ordonnancement
n Règle de déduction decontraintes et de réductionde domaines liée aux pairesde disjonction Tâche 3
Tâche 2
Tâche 1 t
tâches
Propagation
Tâche 3
Tâche 2
Tâche 1 t
tâches
Exemple :
lftj - esti < pi + pj ⇒ i non avant j
problème disjonctif ⇒ j avant i
⇒ ajustements de esti et lftj
est2 lft2
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 20
Propagation de contraintes de temps
n Renforcement de la consistance d'un CSP temporel(TCSP)
– variables = instants– contraintes = distance (sous forme d'un intervalle) entre 2 instants –
exemples : fenêtres temporelles, précédences, délais…
n Problèmes temporels simples (STP)– contrainte ↔ 1 seul intervalle– algorithmes de graphes (Bellman, Ford, Floyd-Warshall…)
n TCSP généraux– contrainte ↔ disjonction d'intervalles– consistance de chemin : PC1, ULT, LPC…
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 21
Propagation de contraintes de ressources
n Opérations locales– paires de disjonction– précédences conjonctives
n ensembles ascendants/descendants
n EFF/LSL
– précédences non conjonctives (NF/NL)
– raisonnement énergétiquen intégration des contraintes temporelles et
de ressource par évaluation d’échangesénergétiques
– entre tâches et ressources– sur des intervalles de temps
n localisation relative ou absolue des tâches A
t1 t2
esti lfti
ai
dis
jon
ctif
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 22
Propagation de contraintes de ressources
n Opérations globales– réfutation d'une décision
par simple propagation sur le problème global– shaving– singleton consistance d'arc
Squelette d'un algorithme SAC
AC(X, D, C)pour x ∈ X et pour v ∈ Dx
x ← v AC(X, D, C ∪ {x ← v}) si inconsistance
C ← C ∪ {¬ (x ← v)}AC(X, D,C)
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 23
Les systèmes de programmation par contraintes
n Pionnier : la programmation logique avec contraintes1982-90 : Prolog II, CLP(R), CHIP, Prolog III
n [Fernandez & Hill, JAIR, 2000] : distingo de 2 types de systèmes :– boîte vitrée (schéma de propagation peut être spécifié par
l'utilisateur)n clp(FD), SICStus, IF/Prolog, CHR
– boîte noire (mécanismes de propagation dont le contrôle échappe àl'utilisateur)
n Oz, ECLiPSe, Ilog SOLVER, B-Prolog
– comparaisons en termes de facilité de prise en main et deperformances sur les domaines des booléens et des domaines finis
n CLAIRE, CHOCOn D'autres encore... voir :
Ô Forum : comp.constraints (FAQ)Ô Roman Barták : http://kti.ms.mff.cuni.cz/~bartak/constraints/
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 24
La programmation par contraintes s'appuie sur :
n les Problèmes de Satisfaction de Contraintes– règles de cohérence locale pour les contraintes temporelles– stratégies de recherche heuristiques
n la Recherche Opérationnelle– procédures arborescentes de résolution– bornes inférieures et supérieures des solutions optimales– règles de propagation des contraintes de ressources
En résumé...
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 25
Paradigme dela programmation par contraintes (3)
Méthode de recherche
CSP
Propagation decontraintes
Définition du problème
contraintes initiales
nouvelle contrainte(décision)
nouvelle contrainte(propagation)
Tiré de Baptiste et al.
26
Pourquoi la programmation par contraintes ?
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 27
Intérêtsde la programmation par contraintes (1)
n nature déclarative des contraintes
n représentation proche du problème originel– variables = entités du problème– contraintes : non nécessairement traduites en inégalités linéaires
n importance des problèmes de satisfiabilité
n modularité (séparation analyse/résolution)è flexibilité des systèmes conçus
n adaptation des algorithmes aux types de contraintes
n efficacité pour certains problèmes (ordonnancement,programmes fortement symétriques)
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 28
Intérêtsde la programmation par contraintes (2)
n aide à la décisionè limitation des actions possibles, explicitation des degrés de liberté
disponibles, caractérisation d'ensembles de solutions admissiblesè comportement réactif (sur la base des CSP dynamiques) adapté a
l'évolution du modèlen importance en pratique de contraintes secondaires pas toujours
intégrées dans la formulation initiale car pas formalisables, tropcontexte-dépendantes
n ajout d'une contrainte → remise en cause des solutions maisconservation des déductions (additivité des contraintes)
n suppression d'une contrainte → remises en cause des déductionsissues de la propagation mais conservation des solutions
n caractère incrémental dans la prise en compte de nouvellescontraintes (sans considération des contraintes existantes ou dela procédure de recherche)
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 29
Inconvénientsde la programmation par contraintes
n modélisationè modeleur (OPL)
n performances, efficacité des techniques de base pour larésolution de grands problèmes
è détermination de bornes inférieures et mécanismes de propagationadaptés
n complétude des déductions, généricité des raisonnementsè structures pour la mise en œuvre de règles de propagation
n sacrifice des caractéristiques générales d'un langage deprogrammation au bénéfice de primitives sophistiquéesdédiées
è librairies
30
Programmation par contraintes,programmation mathématique,
métaheuristiques… ?
l'avenir est à l'hybridation et à la coopérationplus qu'à l'opposition de méthodes
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 31
Quelques ouvrages...
n Constraint-based SchedulingP. Baptiste, C. Le Pape & W.
NuijtenKluwer, 2001
n Logic-based Methods forOptimizationJ. HookerWiley, 2000
n The OPL OptimizationProgramming LanguageP. Van HentenryckMIT Press, 1999
n Intelligence artificielle etinformatique théoriqueJ.-M. Alliot & T. SchiexCépaduès, 1994
n Foundations of ConstraintSatisfactionE. TsangAcademic Press, 1993