Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 15 Janvier 2008

Relaxation de contraintes globales dans le cadre des Weighted CSPs

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

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr