Raisonnement par contraintes

Raisonnement par contraintesCode de l'UE : HMIN330M

Présentation

Le raisonnement par contraintes permet de résoudre de nombreux problèmes combinatoires (emplois du temps, affectation de personnel, etc.). Une solution à un problème de satisfaction de contraintes (ou CSP) est une affectation de valeurs à des variables soumises à des restrictions (= contraintes) sur les combinaisons de valeurs qu'elles peuvent prendre. Nous aborderons rapidement la modélisation de problèmes en CSP et décrirons les principales techniques pour résoudre un CSP. Nous insisterons sur la propagation de contraintes et nous étudierons le concept de contrainte globale, utilisé dans tous les logiciels de résolution de contraintes. Ensuite nous présenterons différentes extensions apportées au modèle CSP pour répondre à des questions plus complexes comme la recherche de la "meilleure" solution selon certains critères. Une partie du cours sur la programmation par contraintes sur intervalles montrera comment ces techniques peuvent s'appliquer dans le monde continu pour résoudre des systèmes de contraintes d'égalités et d'inégalités sur les nombres réels et effectuer de l'optimisation globale sous contraintes.

Volume horaire

  • CM : 13.5
  • TD : 25.5
  • TP : 0
Diplômes intégrant cette UE

En bref

Crédits ECTS 5

Période de l'année
S3

Contact(s)

Composante

Responsable(s)

Souhila KACI (Souhila.Kaci @ univ-montp2.fr)