Résumé
La propagation de contraintes est un composant essentiel de la programmation par contraintes [4]. Les contraintes peuvent être d'arité fixe, c'est à dire définies pour un nombre donné de variables. Par exemple |x−y| = z ou x 6 = y. Mais les contraintes peuvent aussi être "globales", c'est à dire exprimer une propriété pouvant porter sur un nombre quelconque de variables. Par exemple alldifferent spécifie que toutes les variables impliquées, quel que soit leur nombre, doivent prendre des valeurs différentes [10]. Les contraintes d'arité fixe peuvent être propagées en temps polynomial avec un algorithme générique. Les contraintes globales ne peuvent pas être propagées en temps polynomial si on ne dispose pas d'un algorithme ad hoc. Malgré 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'décomposition permet d'exprimer des contraintes globales à partir d'autres contraintes globales ou à partir de contraintes d'arité fixe [9]. Nous montrerons que beaucoup de contraintes globales sont soit NP-difficiles à propager (par exemple Nvalue , Sum ), ce qui lie l'existence de propagateurs polynomiaux à la conjecture P = NP [7], soit d'décomposables en contraintes d'arité fixe préservant la propagation (par exemple Regular , At-most ), ce qui rend l'écriture de propagateurs inutile [2, 5]. Mais nous montrerons aussi que parmi les contraintes globales polynomiales à propager, il y en a qui n'admettent pas de d'décomposition de taille polynomiale en contraintes d'arité fixe préservant la propagation [8]. La contrainte alldifferent , qui admet un propagateur polynomial [12], tombe dans cette catégorie. Ce résultat de non-décomposabilité s'applique aussi aux décompositions 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 définir un ensemble minimal de contraintes globales à implanter dans tout logiciel à contraintes de façon à 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 récemment été étendues à la programmation par fonctions de coût [11]. Nous verrons que l'a aussi, les décompositions peuvent permettre dans certains cas de préserver la propagation [1].