Problèmes à  contraintes valuées et contraintes globales

Encadrants: Christian Bessiere, Thomas Schiex

Les problèmes de satisfaction de contraintes valuées sont une
extension du formalisme CSP qui permet de résoudre des problèmes où
l'on ne peut pas satisfaire complètement toutes les contraintes, mais
seulement essayer de les satisfaire 'au mieux'. Pour cela, chaque
contrainte associe un coût de violation à chaque tuple et le but est
de minimiser la somme des violations. Par ailleurs, le concept de
contrainte globale est une notion importante pour la résolution de
problèmes à contraintes, mais elle a donné lieu à très peu de travaux
dans le cadre valué. 

Le but de ce stage est d'étudier les contraintes globales valuées,
notamment la notion de décomposabilité en contraintes primitives.  Il
s'agit de préserver la sémantique des fonctions de coût et, idéalement
de récupérer les algorithmes de propagation des contraintes primitives
pour propager la contrainte globale décomposée. On peut s'attendre à
des résultats différents de ceux obtenus en satisfaction car il
semblerait que les contraintes de flot puissent être propagées dans le
cas valué alors qu'elles ne peuvent pas l'être dans le cas
satisfaction.  On pourra aussi étudier les liens entre la notion de
décomposabilité et la notion de contractibilité des contraintes
globales introduite par Maher en 2009.