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 (PSC) 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 PSC.
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 (domaines, variables, contraintes globales, buts de recherche) d'une bibliothèque de Programmation par Contraintes (PPC) pour des langages différents de Prolog.
Modéliser et résoudre des problèmes d'optimisation combinatoire avec la PPC.
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. Nécessite des connaissances en programmation fonctionnelle (OCaml).

Volume horaire (h)

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

Examens

Nombre total d'heures d’évaluation : 2