% DIC938N — Programmation par contraintes % UQAM — Département d'informatique % Plan de cours — Hiver 2023 * Horaires, locaux et enseignants: Enseignement ============ Avellaneda, Florent PK-4435 Groupes: 020 Description du cours ==================== La programmation par contraintes est un paradigme de programmation permettant de résoudre efficacement des problèmes combinatoires de grande taille. Ce paradigme consiste à modéliser les problèmes à l'aide de variables de décision associées à un ensemble de contraintes et éventuellement à une fonction de coût. Bénéficiant de décennies de recherche, des solveurs peuvent ensuite être utilisés pour résoudre efficacement ces modélisations. Dans ce cours, nous nous intéresserons à deux types de problèmes, les problèmes de décision et les problèmes d'optimisation. Nous aborderons des modélisations en SAT et SMT pour les problèmes de décision, et des modélisations en MaxSAT, en programmation linéaire et par recherche locale pour les problèmes d'optimisation. Nous explorerons le fonctionnement de ces solveurs de contraintes et apprendrons à modéliser efficacement les problèmes dans différents langages de modélisation. Objectif du cours ================= Les objectifs spécifiques de ce cours sont : - Comprendre le fonctionnement des différents solveurs de contraintes ; - Maîtriser la modélisation des problèmes sous forme de contraintes ; - Explorer différentes techniques d'optimisation. Contenu du cours ================ **Problème de satisfaction de contraintes** - SAT - SMT - Logique monadique du second ordre **Problème d'optimisation sous contraintes** - MaxSAT - Programmation linéaire - Recherche locale Modalités d'évaluation ====================== Description sommaire Pondération ------------------------------------------- ------------- Travaux pratiques pendant la session 30% Présentation orale à la fin de la session 30% Rapport écrit 40% La note finale (en lettre, A+, A, etc.) pour le trimestre sera attribuée en fonction de l'atteinte des objectifs spécifiques à travers les évaluations. La distribution des résultats dans le groupe pourrait aussi être utilisée. Aucune autre opportunité (travail supplémentaire, etc.) d'augmenter le nombre de points ne sera accordée. Références ========== Obligatoires : - Transparents et annexes disponible sur le site web du cours Utiles : - Handbook of Constraint Programming. F. Rossi, P. Van Beek, T. Walsh. - Handbook of satisfiability. A. Biere, M. Heule, H. van Maaren.