Arnaud Lalouet (GREYC)

Les CSP quantifiés, ou QCSP sont un moyen de modéliser des problèmes avec adversaire ou des problèmes comportant de l’incertain. En disposant d’un langage de contraintes expressif, il est possible en QCSP d’exprimer des formules du type : est ce qu’il existe un X tel que pour tout Y , C ( X , Y ) soit vrai. La première technique pratique de résolution de tels problèmes (Bordeau et Monfroy, 2002) a proposé la définition de l’arc- consistance quantifiée, plus puissante que l’arc-consistance classique et qui permet de filtrer les domaines des variables existentielles. Hélas le QCSP en forme prénexe ne facilite pas la modélisation et peu d’applications ont été réalisées.

Avec le projet QeCode, nous proposons un solveur permettant de résoudre des QCSP utilisant un langage plus étendu, avec des quantificateurs restreints. Non seulement la modélisation devient plus intuitive, mais il devient possible de filtrer les variables universelles. QeCode est basé sur le solveur de contraintes Gecode dont il permet de réutiliser toutes les contraintes et leurs opérateurs de filtrage, y-compris les contraintes globales.

Pour finir, nous présenterons un schéma d’optimisation dans le cadre quantifié, et nous montrerons qu’il permet de représenter des problèmes de décision à plusieurs niveaux connus sous le nom de bi-level programming. Nous montrerons deux applications industrielles de ces techniques dans le cas linéaire, sachant que QeCode autorise l’extension au cas discret et aux contraintes quelconques.