31
P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 1 Le concept de contraintes : propagation, satisfaction, programmation Pierre Lopez LAAS, Toulouse

Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 1

Le concept de contraintes :propagation, satisfaction, programmation

Pierre LopezLAAS, Toulouse

Page 2: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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

Page 3: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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)

Page 4: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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

Page 5: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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

Page 6: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

6

et la programmation par contraintes...

Page 7: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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)

Page 8: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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)

Page 9: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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

Page 10: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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…

Page 11: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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

Page 12: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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

Page 13: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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

Page 14: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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

Page 15: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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

Page 16: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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

Page 17: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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]

Page 18: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

18

le temps et les ressources...

Page 19: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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

Page 20: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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…

Page 21: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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

Page 22: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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)

Page 23: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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/

Page 24: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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é...

Page 25: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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.

Page 26: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

26

Pourquoi la programmation par contraintes ?

Page 27: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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)

Page 28: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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)

Page 29: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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

Page 30: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

30

Programmation par contraintes,programmation mathématique,

métaheuristiques… ?

l'avenir est à l'hybridation et à la coopérationplus qu'à l'opposition de méthodes

Page 31: Le concept de contraintes : propagation, satisfaction ...P. Lopez : "Contraintes" GRP - Toulouse, Novembre 2001 2 Préambule n Présentation des concepts de base liés au raisonnement

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