• Votre sélection est vide.

    Enregistrez les diplômes, parcours ou enseignements de votre choix.

Approches exactes de résolution

  • ECTS

    3 crédits

  • Composante

    Faculté des sciences

Description

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.

Lire plus

Objectifs

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

Lire plus

Heures d'enseignement

  • CMCours magistral15h
  • TDTravaux dirigés15h

Pré-requis obligatoires

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 

Lire plus