Problèmes de satisfaction de contraintes avec des variables ensemblistes
et critères d'optimisation
Les problèmes de satisfaction de contraintes (ou CSP) sont des problèmes
combinatoires définis par une ensemble de variables soumises à
un ensemble de contraintes et prenant leurs valeurs dans un ensemble de
domaines associés. Lorsqu'un problème NP-complet est modélisé
par un CSP, on peut restreindre l'espace de recherche des solutions en
utilisant des techniques de consistance. De telles règles de filtrage
ont pour but d'éliminer des domaines les valeurs dont on est sûr
qu'elles ne pourront faire partie d'aucune solution.
L'utilisation de variables multi-valuées (dont la valeur est
un ensemble de termes) s'est révélé être un
moyen efficace pour représenter des solutions multiples de certains
CSP, empêchant la répétition ou la précédence
des valeurs. Dans ce contexte, nous appelons CSP ensembliste, un CSP dont
chaque variable est multi-valuée et ne peut prendre que des ensembles
de termes de profondeur un (des ensembles d'ensembles de termes ne sont,
par exemple, pas autorisés).
Parce qu'ils modélisent un grand nombre de problèmes
comme l'analyse de programmes, l'inférence de types, les arbres
à automates, des problèmes combinatoires issus du domaine
de la recherche opérationnelle, les contraintes ensemblistes sont
d'un intérêt croissant.
Publication
V. Thornary, J.
Gensel, A hybrid representation for set constraint satisfaction
problems, Workshop on Set Constraints, Fourth International
Conference on Principles and Practice of Constraint Programming, Pisa,
Italy,
October
26-30, 1998. [postscript gzippé][pdf]
Dernière mise à jour : 4 Avril 2000
