Problème de satisfaction de contraintes

Les problèmes de satisfaction de contraintes ou CSP (Constraint Satisfaction Problem) sont des problèmes mathématiques où l'on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Les CSP font l'objet de recherches intenses à la fois en intelligence artificielle et en recherche opérationnelle. De nombreux CSP nécessitent la combinaison d'heuristiques et de méthodes d'optimisation combinatoire pour être résolus en un temps raisonnable. Ils sont notamment au cœur de la programmation par contraintes, un domaine fournissant des langages de modélisation de problèmes et des outils informatiques les résolvant.

Définition formelle

Formellement, un problème de satisfaction de contraintes est défini par un triplet $\langle X,D,C\rangle$ , où $X$ est un ensemble de $n$ variables, $D$ est un ensemble de $n$ domaines de valeurs tels qu'un de ses éléments $d_{i}$ soit le domaine d'une variable $x_{i}$ de $X$ , et $C$ est un ensemble de contraintes. Chaque contrainte est à son tour une paire $\langle t,R\rangle$ , où $t$ est un N-uplet de variables et $R$ est un ensemble de N-uplets de valeurs ; tous ces N-uplets ayant le même nombre d'éléments ; ainsi $R$ définit une relation. Une évaluation des variables est une fonction des variables vers les domaines, $v:X\rightarrow D$ . Une telle évaluation satisfait une contrainte $\langle (x_{1},\ldots ,x_{n}),R\rangle$ si $(v(x_{1}),\ldots ,v(x_{n}))\in R$ . Une solution est une évaluation qui satisfait toutes les contraintes.

Aspects théoriques des CSP

Les CSP sont aussi étudiés en théorie de la complexité des algorithmes et en théorie des modèles finis. Une question importante est de savoir si pour chaque ensemble de relations, l'ensemble de tous les CSP qui peuvent être représentés uniquement par des relations choisies à partir de cet ensemble est soit de classe P soit NP-complet (en présumant P ≠ NP). Si une telle dichotomie est vraie, alors les CSP fournissent l'un des plus larges ensembles connus de NP, évitant les problèmes qui ne sont ni résolubles en un temps polynomial ni NP-complets, dont l'existence fut démontrée par le théorème de Ladner. La dichotomie est connue pour des CSP où le domaine de valeurs est de taille 2 ou 3. Deux communications, parues simultanément en 2017, l'une de Dmitriy Zhuk^[1] et l'autre de Andrei Bulatov^[2] présentent des solutions du problème général.

La plupart des CSP connus pour être faciles à aborder sont ceux où l'hypergraphe de contraintes a une largeur arborescente limitée (et où il n'y a aucune restriction sur l'ensemble des relations représentant les contraintes), ou alors, les contraintes ont une forme arbitraire mais il existe essentiellement des polymorphismes non-unaires^[Quoi ?] de cet ensemble de relations de contrainte.

Applications

Parmi les problèmes pouvant être modélisés par un CSP, on compte : le problème des huit dames, le problème du théorème des quatre couleurs, le jeu de sudoku, la satisfiabilité booléenne et le problème du sac à dos.

Algorithmes

Les algorithmes utilisés pour résoudre des problèmes de satisfaction de contraintes incluent les algorithme de propagation de contraintes, le retour sur trace (et son évolution non chronologique), l’apprentissage de contraintes (en) et l'algorithme des conflits minimaux (en).

Voir aussi

Bibliographie

Blaise Madeline, Algorithmes évolutionnaires et résolution de problèmes de satisfaction de contraintes en domaines finis (thèse, 2002)
Christine Solnon, Programmation par Contraintes (cours, 2003)
Pierre Lopez, Le concept de contraintes : propagation, satisfaction, programmation (diaporama, 2001)
(en) Edward Tsang (en), Foundations of Constraint Satisfaction, London/San Diego, Academic Press, 1993 (ISBN 978-0-12-701610-8, présentation en ligne)
(en) Rina Dechter, Constraint processing, San Francisco, Morgan Kaufmann (en), 2003 (ISBN 978-1-55860-890-0, présentation en ligne, lire en ligne)
(en) Krzysztof Apt, Principles of constraint programming, CUP, 2003, 407 p. (ISBN 978-0-521-82583-2, lire en ligne)
(en) Christophe Lecoutre, Constraint Networks : Techniques and Algorithms, ISTE/Wiley, 2009 (ISBN 978-1-84821-106-3, présentation en ligne)
(en) Tomás Feder, Constraint satisfaction: a personal perspective (preprint)
(en) Constraints archive
(en) CSPLib : a problem library for constraints
(en) Forced Satisfiable CSP Benchmarks of Model RB
(en) Benchmarks -- XML representation of CSP instances

Notes et références

↑ Dmitriy Zhuk, « A Proof of the CSP Dichotomy Conjecture », 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE,‎ 2017, p. 319–330 (DOI 10.1109/FOCS.2017.38)
↑ Andrei A. Bulatov, « A Dichotomy Theorem for Nonuniform CSPs », 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE,‎ 2017, p. 319–330 (DOI 10.1109/FOCS.2017.37).

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Constraint satisfaction problem » (voir la liste des auteurs).

Portail de l'informatique théorique

[1] Dmitriy Zhuk, « A Proof of the CSP Dichotomy Conjecture », 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE,‎ 2017, p. 319–330 (DOI 10.1109/FOCS.2017.38)

[Bulatov2017-2] Andrei A. Bulatov, « A Dichotomy Theorem for Nonuniform CSPs », 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE,‎ 2017, p. 319–330 (DOI 10.1109/FOCS.2017.37).

[1]

[2]