État de l'art

Les contraintes globales sont des techniques qui permettent de traiter un sous-ensemble de contraintes du même type plus efficacement que les méthodes traditionnelles. La plupart des travaux existants portent sur des CSP dont les variables varient dans des domaines finis. Dans les domaines continus il n'existe, à notre connaissance, qu'une seule contrainte globale c'est la méthode du simplexe, limitée à des contraintes linéaires. La méthode du simplexe est la plus utilisée lorsqu'on veut résoudre un système d'equations et/ou d'inequations linéaires avec ou sans optimisation d'une fonction linéaire. Pour plus de détails, nous citons les ouvrages de référence de Greenwald[5] et Papadimitriou [7]. Trouver une contrainte globale dans les domaines continus constitue une nouveauté dans le cadre de la programmation par contrainte. Nous allons tout d'abord présenter la consistance d'arc dans les domaines finis. Afin de comprendre l'intérêt des contraintes globales nous étudierons brièvement la contrainte all-diff [10]. Enfin nous nous attarderons plus en détail sur les méthodes de filtrage local : 2B-consistance et 3B-consistance [16,15,6], les méthodes les plus utilisées dans les domaines continus, basées sur l'arithmétique des intervalles[17] et la consistance d'arc[1]. Les méthodes de filtrage local permettent de résoudre des CSP dans le cadre géneral, on étudiera dans ce chapitre quelles sont leurs limites et leurs difficultés pour les problèmes de satisfaction de contraintes de distance.