Achref El Mouelhi

Le problème de satisfaction des contraintes CSP (pour Constraint Satisfaction Problems en anglais) est connu pour être NP-complet, même pour le cas binaire. Cependant, en imposant certaines restrictions, sur la taille des domaines ou sur les contraintes, la résolution peut être accomplie en temps polynomial. Dans ce cas, on parle des propriétés traitables (tractables properties). L’ensemble d’instances satisfaisant une propriété traitable constitue une classe polynomiale (ou traitable). Par exemple, Il est connu que l’ensemble des instances qui satisfont la propriété des triangles cassés BTP (pour Broken-Triangle Property) ou ZOA (Zero/One/All) définissent des classes polynomiales pour les CSP binaires. En pratique, les classes polynomiales sont rarement présentes. En plus, elles nécessitent généralement des algorithmes ad-hoc pour la reconnaissance et pour la résolution. Par conséquent, les algorithmes de l’état de l’art comme, FC (pour Forward Checking), RFL (pour Real Full Lookahead) ou MAC (pour Maintaining Arc-Consistency) ne peuvent pas les exploiter. Récemment, des efforts considérables ont été consacrés à l’identification des classes polynomiales qui sont facilement exploitées par les algorithmes de l’état de l’art cités ci-dessus. Par exemple, il a été prouvé que l’ensemble d’instances CSP ayant un nombre polynomial de cliques maximales dans le graphe de microstructure peuvent être résolues en temps polynomial par les algorithmes de résolution classiques. Ensuite, un nouveau cadre dont le but est d’étendre le champ des classes polynomiales a été proposé. En effet, il est basé sur la notion de transformation de CSP et introduit la notion de classe polynomiale cachée. Elle part du constat selon lequel les problèmes réels n’appartiennent pas en général à des classes polynomiales mais peuvent parfois, après simplification (en appliquant certains algorithmes de filtrages par cohérence locale, par exemple) en faire partie. Aussi, certains travaux ont montré que les propriétés traitables peuvent être utilisées pour éliminer des variables, fusionner des valeurs ou décomposer des contraintes tout en préservant la satisfiabilité. Plus précisément, l’absence de triangles cassés sur tous les couples de valeurs d’une variable d’une instance CSP arc-cohérente autorise l’élimination de cette variable sans affecter la satisfiabilité de l’instance. L’absence de triangles cassés sur un couple de valeurs d’une même variable d’une instance CSP donnée permet également de les fusionner sans modifier la satisfiabilité de l’instance.

Mots clés : CSP, propriété traitable, triangle cassé, fusion de valeurs, élimination de variables.