Objectifs
Ce cours adresse des modèles de traitement efficace des données rencontrées dans des problèmes industriels à caractère combinatoire. Les modèles sont basés sur le raisonnement logique et l'optimisation : les problèmes de satisfaction de contraintes (PPC), les problèmes de satisfiabilité booléenne (SAT/SMT) et la programmation linéaire en nombres entiers (PLNE). Pour la partie PPC, les étudiants doivent connaître les principales techniques de propagation et de résolution et se familiariser, à travers les travaux pratiques, avec des outils de programmation intégrant des algorithmes de propagation de contraintes et des stratégies de branchement ainsi que d'autres techniques avancées de résolution (ex d'outil : CPLEX, CPMpy). Dans la partie SAT, les étudiants implémentent un solveur SAT basé sur l'algorithme d'apprentissage de clauses dirigé par les conflits (CDCL) et découvrent les modèles à base de 'satisfiabilité modulo théories' (SMT). Différents problèmes combinatoires classiques (coloration, affectation de ressources, ordonnancement) servent de cas pratiques pour s'entraîner sur l'encodage SAT.
Pour la partie PLNE, les étudiants doivent modéliser des problèmes industriels sous forme de programme linéaire en nombre entiers, et les résoudre via des algorithmes de branchement ou des méthodes de décomposition en utilisant des outils de programmation (CPLEX).
Pré-requis
Algorithmics & programming (I2MIIF11, I2MIIF21).
Fundamentals in Computer Science (I4IRIF11),
Intelligent Systems (I4IRSD11)
Évaluation
L’évaluation des acquis d’apprentissage est réalisée en continu tout le long du semestre. En fonction des enseignements, elle peut prendre différentes formes : examen écrit, oral, compte-rendu, rapport écrit, évaluation par les pairs…
