Introduction à la Programmation par Contraintes Cours 1. Problèmes de Satisfact

Introduction à la Programmation par Contraintes Cours 1. Problèmes de Satisfaction de Contraintes. Ruslan Sadykov INRIA Bordeaux — Sud-Ouest 22 Septembre 2014 1 / 52 Organisation du cours ▶5 cours + 2 TD + 5 TP . ▶2 TD : exercices sur le papier ▶2-3 TP : introduction à un solveur PPC ▶2-3 TP : projet ▶Évaluation : 50% de la note pour le projet + 50% de la note d’examen. ▶La page du cours : www.math.u-bordeaux.fr/ ~sadykov/teaching/MSE3315C/ 2 / 52 Lignes directrices Introduction Applications de PPC Problèmes de Satisfaction des Contraintes Exemples de modélisation Résolution 3 / 52 Qu’est-ce que c’est la PPC ? Une technique mathématique pour résoudre des problèmes combinatoires Ça marche en trois phases Modélisation Vous définissez votre problème dans un format spécifique Implémentation Vous écrivez votre modèle dans un langage de modélisation Résolution Vous utiliser un solveur PPC (compatible) pour trouver une solution 4 / 52 Limitations de PPC La PPC n’est surtout pas ▶une méthode magic ▶A priori,elle n’est pas meilleure que d’autres méthodes (programmation linéaire, programmation dynamique, recherches locales, etc...) ▶Tout dépend du type de problème ! ▶une méthode « press button » , du moins pour l’instant ▶Nécessité de comprendre la technique ▶Nécessité de « guidez » la résolution Source : Antoine Jeanjean 5 / 52 Les objectives du cours ▶Savoir pour quels types de problèmes la méthode de PPC est bonne ▶Savoir modéliser efficacement ces problèmes ▶Connaître les langages de modélisation et solveurs PPC et savoir les utiliser ▶Savoir comment les solveur marchent à l’intérieur 6 / 52 Spécificités de PPC ▶On travaille avec un problème de décision — le Problème de Satisfation des Contraintes (CSP) (avec une série des CSPs, si c’est un problème d’optimisation) ▶Grandes possibilités de modélisation (contraintes non-linéaires, logiques, explicites) ▶Utilisation des contraintes du problème de manière active pour limiter l’espace de recherche (Plus il y a des contraintes, plus facile à résoudre le problème) 7 / 52 Un exemple introductive — Sudoku 3 4 5 7 6 2 8 4 7 1 9 2 6 3 8 2 3 1 3 6 9 5 8 4 7 6 9 5 3 8 2 ▶Il y a 81 cases où on peut mettre les chiffres de 1 à 9 ▶On doit mettre les chiffres dans les cases tel que chaque horizontale (verticale, bloque de 9 cases) contienne les chiffres différents. On vient (presque) de formuler un Problème de Satisfaction de Contraintes( !) En PPC, le problème est résolu exactement plus ou moins de la même façon que vous résolvez le sudoku( !) 8 / 52 Lignes directrices Introduction Applications de PPC Problèmes de Satisfaction des Contraintes Exemples de modélisation Résolution 9 / 52 Domaines d’application ▶Agencement ▶Diagnostique et Vérification ▶Planification ▶Ordonnancement et Empois du temps ▶Emballage et Placement ▶Logistique 10 / 52 Application réelle I — Ligne de production des voitures Source : Alan M. Frisch 11 / 52 Application réelle II — Étiquetage de scènes On a un dessin vectoriel d’une scène contenant des objets planaires avec des sommets trièdres. But : reconnaître ces objets, c’est-à-dire donner aux arrêtes une des 4 étiquettes possibles : ▶+ (l’arrêt concave), ▶−(l’arrêt convexe), ▶→ou ←(l’objet à droite, l’arrière-plan à gauche). Source : (Liu, Young, Das, 88) 12 / 52 Application réelle II — Étiquetage de scènes (cont.) 16 jonctions possibles : + _ _ _ + + + + _ _ _ _ _ _ + + + _ + _ + Étiquetage possible : + + + + + + _ 13 / 52 Application réelle III — Calendrier sportif Il y a plusieurs équipes sportif. Dans le championnat, chaque équipe dois jouer avec toutes les autres. Il faut trouver un calendrier : déterminer pour chaque journée, qui joue contre qui. Des contraintes additionnelles peuvent être imposées. Jour 1 Jour 2 Jour 3 Jour 4 Jour 5 Jour 6 Jour 7 1 vs 8 2 vs 8 4 vs 7 3 vs 6 3 vs 7 1 vs 5 2 vs 4 2 vs 3 1 vs 7 3 vs 8 5 vs 7 1 vs 4 6 vs 8 5 vs 6 4 vs 5 3 vs 5 1 vs 6 4 vs 8 2 vs 6 2 vs 7 7 vs 8 6 vs 7 4 vs 6 2 vs 5 1 vs 2 5 vs 8 3 vs 4 1 vs 3 14 / 52 Application plus « fun »— Portraits de dominos But : trouver une bonne approximation d’une image réalisée à partir des dominos d’un nombre donné de boites. Exemple à droite : Un portrait de George Boole, puis une séquence de portraits de dominos générés à partir de cette image et utilisant 1, 4 et 16 boites do dominos. Actes JFPC 2008 G´ en´ eration efficace de portraits de dominos Hadrien Cambazard John Horan Eoin O’Mahony Barry O’Sullivan Cork Constraint Computation Centre Department of Computer Science, University College Cork, Ireland {h.cambazard|j.horan|e.omahony|b.osullivan}@4c.ucc.ie R´ esum´ e Un portrait de dominos est une approximation d’une image r´ ealis´ ee a partir des dominos d’un nombre donn´ e de boites. Ce probl` eme fut pos´ e la premi` ere fois en 1981 et des portraits de dominos ont ´ et´ e obtenus depuis par des techniques de programmation lin´ eaire, capables de produire des solutions optimales mais qui restent tr` es lentes et incapables de passer ` a l’´ echelle. Nous propo- sons dans cet article une nouvelle approche qui supprime ces limitations et produit des portraits de haute qualit´ e. Elle repose sur des techniques de recherche op´ eration- nelle, de programmation par contraintes et de traitement d’image. Son efficacit´ e r´ esulte de la r´ esolution d’un flot ` a coˆ ut minimum identifi´ e comme le coeur du probl` eme. Elle fournit des portraits qu’on peut difficilement dis- tinguer visuellement de l’optimum dans des temps de r´ esolution beaucoup plus faibles. 1 Introduction En 1981, Kenneth Knowlton d´ eposa un brevet aux Etats Unis intitul´ e “Representation of Designs” [4] dans lequel il proposait de produire des images monochromes en utilisant des dominos. Vingt ans plus tard, Robert Bosh expliquait ` a CP-AI-OR 2006 (Constraint Programming, Artificial Intelligence and Operations Research) comment les techniques d’opti- misation peuvent ˆ etre utilis´ ees dans un contexte artis- tique de cr´ eation d’images et de portraits en soulignant les qualit´ es artistiques des images g´ en´ er´ ees tout comme plet (domino vierge) jusqu’au blanc presque complet (domino 9-9). Fig. 1 – Un portrait de George Boole est pr´ esent´ e sur la gauche, puis une s´ equence de portraits de dominos g´ en´ er´ es ` a partir de cette image et utilisant 1, 4 et 16 boites de dominos. Un ensemble de dominos se pr´ esente ainsi comme une palette de niveaux de gris qui est utilis´ ee pour g´ en´ erer l’image. Cette palette est contrainte dans la mesure o` u une boite ne contient qu’un seul domino de chaque type et qu’on ne peut pas ”briser” un do- mino en deux mais qu’on doit utiliser la pi` ece dans son Source : (Cambazard, Horan, O’Mahony, O’Sullivan, 2008) 15 / 52 Applications réelles au Bouygues e-lab ▶Les plans de tables pour le conférences du groupe ▶La planification des Corps d’État Secondaires sur les chantiers de construction ▶La planification de personnel ▶La planification de campagnes marketing ▶Projet exploitants la technique ▶La planification de la publicités (sur TF1) ▶La planification de « call-centers » Source : Antoine Jeanjean 16 / 52 D’autres applications Plus d’application sur le site www.csplib.org Il y en a 50 ! 17 / 52 Applications dans la recherche Informatique Analyse de programme, Robotique Biologie Repliement de protéine, Séquençage de l’ADN Économie Ordonnancement Linguistique Analyse grammaticale Médecine Aide à la diagnostique Physique Modélisation d’un système Géographie Systèmes de géoinformation 18 / 52 Lignes directrices Introduction Applications de PPC Problèmes de Satisfaction des Contraintes Exemples de modélisation Résolution 19 / 52 Problème de Satisfaction des Contraintes (CSP) CSP est un triplé ⟨X, D, C⟩, où : ▶X est un ensemble des variables {x1, . . . , xn}, ▶D est un ensemble des domaines {Dx1, . . . , Dxn} (ensembles des valeurs possibles) pour ces variables, ▶C est un ensemble des contraintes  Ci(xi1, . . . , xni) i∈|C| . Chaque contrainte Ci restreint les valeurs que les variables {xi1, . . . , xin} peuvent prendre simultanément. 20 / 52 Domaines Les domaines peuvent être ▶ensembles finis : {1, 2, . . . , n}, {2, 3, 5}, {rouge, noir, bleu}; ▶intervalles : [0, k], [1.2, 5.9]; ▶arbres (pas dans ce cours). 21 / 52 Contraintes Les contraintes peuvent être ▶logiques : x = 1 ou y = 3, x = 2 ⇒y = 4; ▶arithmétiques : x > y, z = 2x + 3y −5; ▶explicites (n-tuples des valeurs possibles) : (x, y) ∈  (0, 0), (1, 0), (2, 2) , (x, y, z) ∈  (1, 2, 3), (2, 3, 4) ; ▶complexes (globales) : all −different(x1, uploads/Voyage/ ppc14-cours1-print.pdf

Documents similaires

j j j j j j j j j j j j j j j j j j Illustration de couverture: © 5 rue virtuel 0 0

4 FICHE ACTIVITE DEMARCHE DE PROJET Séquence 2 Intercalaire "ACTIVITES" Fiche 4 0 0

R. Fathallah Bonne Chance. 1/2 المدرســـ ة الوطني ــــ ة للمهندسي ــــ ن بسوس ـ 0 0

Distribution : Voir liste Secrétariat: EST-ME/Francoise Girard-Madoux CERN CH 1 0 0

TLS Théorie des Contraintes + Lean + Six Sigma - Point de Vue - Paris, le 3 sep 0 0

1 Revue Construction Métallique CALCUL DES CONTRAINTES DANS UN ÉLÉMENT SOUMIS À 0 0

1 sur 4 ________________________________________________________________ GEC 50 0 0

 LES RESIDENCES DE TOURISME ET LES VILLAGES DE VACANCES Conjoncture et prévisi 0 0

Laboratoire de Métallurgie Physique Département des Matériaux EPFL Cours Millie 0 0

Contraintes dans une poutre en flexion STR5 Manuel de l’étudiant TecQuipment LT 0 0

• Détails
• Publié le Jul 30, 2022
• Catégorie Travel / Voayage
• Langue French
• Taille du fichier 1.2654MB