IP5003 - Programmation par contraintes

Objectifs

Objectif général :

Modéliser et résoudre des problèmes d'optimisation combinatoire grâce à la programmation par contraintes.

Objectifs détaillés :

Comprendre le formalisme des problèmes de satisfaction de contraintes (CSP) et comment il permet de représenter des problèmes d'optimisation combinatoire. Comprendre la propagation des contraintes et savoir établir la cohérence d'arc sur un CSP. Comprendre les algorithmes de résolution Branch & Prune et d'optimisation Branch & Bound, ainsi que les enjeux des stratégies de recherche. Maîtriser les concepts de bases d'une bibliothèque de Programmation par Contraintes (CP) pour des langages différents de Prolog (domaines, variables, contraintes globales, buts de recherche). Modéliser des problèmes d'optimisation combinatoire à l'aide des CSP et développer efficacement des solveurs. Expérimenter différentes stratégies de recherche. Appréhender les notions de rupture de symétrie et de contraintes redondantes.

Place dans le cursus

Doit se situer après le cours de programmation logique.

Volume horaire (h)

• Cours Magistraux : 10h
• Travaux Pratiques : 12h

Examens

Nombre total d'heures d’évaluation : 2