Contraintes globales et décompositions

La propagation de contraintes est un composant essentiel de la programmation par contraintes [4]. Les contraintes peuvent etre d'arite fixe, c'est a dire definies pour un nombre donne de variables. Par exemple |x−y| = z ou x 6 = y. Mais les contraintes peuvent aussi etre "globales", c'est a dire exprimer une propriete pouvant porter sur un nombre quelconque de variables. Par exemple alldifferent specifie que toutes les variables impliquees, quel que soit leur nombre, doivent prendre des valeurs differentes [10]. Les contraintes d'arite fixe peuvent etre propagees en temps polynomial avec un algorithme generique. Les contraintes globales ne peuvent pas etre propagees en temps polynomial si on ne dispose pas d'un algorithme ad hoc. Malgre tout, depuis 15 ans, les contraintes globales se sont rendues indispensables parce que quand on dispose d'un algorithme pour les propager, elles permettent souvent une propagation forte [13]. Il existe plus de 300 contraintes globales [3] mais la notion de d'decomposition permet d'exprimer des contraintes globales a partir d'autres contraintes globales ou a partir de contraintes d'arite fixe [9]. Nous montrerons que beaucoup de contraintes globales sont soit NP-difficiles a propager (par exemple Nvalue , Sum ), ce qui lie l'existence de propagateurs polynomiaux a la conjecture P = NP [7], soit d'decomposables en contraintes d'arite fixe preservant la propagation (par exemple Regular , At-most ), ce qui rend l'ecriture de propagateurs inutile [2, 5]. Mais nous montrerons aussi que parmi les contraintes globales polynomiales a propager, il y en a qui n'admettent pas de d'decomposition de taille polynomiale en contraintes d'arite fixe preservant la propagation [8]. La contrainte alldifferent , qui admet un propagateur polynomial [12], tombe dans cette categorie. Ce resultat de non-decomposabilite s'applique aussi aux decompositions en SAT : la propagation unitaire sur un nombre polynomial de clauses ne peut pas simuler la propagation de toutes les contraintes globales polynomiales. Une alternative possible pour contourner cette limitation serait de definir un ensemble minimal de contraintes globales a implanter dans tout logiciel a contraintes de facon a pouvoir exprimer et propager toutes les autres. Nous montrerons quelques exemples de tentatives pour proposer des contraintes globales de base permettant d'en exprimer beaucoup d'autres [2, 6]. Mais la question de cet ensemble minimal de contraintes reste ouverte. Les contraintes globales ont recemment ete etendues a la programmation par fonctions de cout [11]. Nous verrons que l'a aussi, les decompositions peuvent permettre dans certains cas de preserver la propagation [1].