Approches exactes de résolution

L’objectif de ce cours est d’appréhender les concepts et méthodes fondamentaux permettant de modéliser et résoudre de manière exacte des problèmes d’optimisation combinatoire et de satisfaction de contraintes.  

Dans le cadre des problèmes de satisfaction de contraintes seront présentées les méthodes de recherche arborescente, heuristiques de branchement, maintien de consistance, élimination de symétries, utilisation de contraintes globales, décomposition et hybridation avec méthodes de recherche locale.  

Les analyses de modèles, la reformulation, la conversion de modèles seront également abordés dans le cadre de la modélisation par contraintes.

— Connaître les méthodes générales de filtrage de problèmes 
— Être capable de comparer et analyser deux modèles d’un même problème, et éviter les phénomènes comme la symétrie et les big M
—  Connaître et être capable d'implanter les techniques de résolution de contraintes : fermeture par consistance locale, backtracking et couplage avec propagation de contraintes, heuristiques, élimination de symétries.
—  Savoir utiliser des contraintes globales et en connaître les méthodes de propagation sur quelques cas.
—  Savoir identifier des classes d’applications où la programmation par contraintes peut être utilisée à bon escient. 

Notions
UE Intelligence Artificielle et Optimisation 1 en M1 

Contenus
— Savoir modéliser un problème sous contraintes
— Savoir dérouler un algorithme de filtrage