Jean-Philippe Métivier (GREYC, Caen)

Dans le cadre de la programmation par contraintes, les contraintes globales ont amenées une évolution majeure aussi bien du point de vue de la modélisation (en synthétisant des ensembles de contraintes) que de la résolution (grâce a des techniques héritées d’autres domaines comme la recherche opérationnelle ou la programmation logique).

Par ailleurs du fait que beaucoup de problèmes sont sur-contraints (ne possèdent pas de solution). Pour résoudre ce type de problème, le cadre des CSPs a été étendu au cadre des CSPs valués. Dans ce cadre, on cherche une instanciation complète minimisant un critère d’insatisfaction (minimiser le nombre de contraintes violées pour les Max-CPSs, minimiser le poids des contraintes violées pour les WCSPs).

Dans cet exposé, nous étudierons deux contraintes globales très utilisées dans des problèmes industriels (comme l’allocation de ressources) : AllDifferent et Gcc. Pour ces deux contraintes, nous les présenterons dans le cadre des CSPs puis nous présenterons leurs premières extension dans les Max-CSPs. Ensuite, nous présenterons nos trauvaux sur la relaxation de ces contraintes dans les WCSPs.