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 Décembre 2009

Contraintes quantifiées : satisfaction et optimisation

par Jérémie Vautard (GREYC)

Les problèmes de satisfaction de contraintes quantifiées (QCSP) sont une extension des problèmes de satisfaction de contraintes dans laquelle certaines des variables peuvent être quantifiées universellement. Un tel formalisme permet de représenter de manière compacte des jeux à deux joueurs ("Existe-t-il un coup tel que pour tout coup de mon adversaire, il existe un coup tel que pour tout coup de mon adversaire ..... tel que je gagne ?") ou, plus généralement, toute une classe de problème dans lesquels certains paramètres ne sont pas contrôlables (par exemple, la réalisation d'un projet en présence d'un ennemi ayant pour objectif de l'empêcher). Après avoir présenté les limitations du formalisme "classique" des QCSP, j'exposerai mes travaux sur deux extensions de ce cadre : d'une part, les QCSP+, permettant de modéliser aisément des problèmes non-triviaux ; et d'autre part la version "optimisation" de ces problèmes : les QCOP+, permettant de représenter et de résoudre des problèmes d'optimisation multi-niveaux non-linéaires. Enfin, je présenterai plusieurs pistes pour des travaux futurs.

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