Programmation par contraintes

La programmation par contraintes (PPC, ou CP pour constraint programming en anglais) est un paradigme de programmation apparu dans les années 1970 et 1980 permettant de résoudre des problèmes combinatoires de grande taille tels que les problèmes de planification et d'ordonnancement. En programmation par contraintes, on sépare la partie modélisation à l'aide de problèmes de satisfaction de contraintes (ou CSP pour Constraint Satisfaction Problem), de la partie résolution dont la particularité réside dans l'utilisation active des contraintes du problème pour réduire la taille de l'espace des solutions à parcourir (on parle de propagation de contraintes).

« En informatique, de toutes les approches en programmation, la programmation par contraintes se rapproche le plus de l'idéal : l'utilisateur décrit le problème, l'ordinateur le résout. »

— E. Freuder

Dans le cadre de la programmation par contraintes, les problèmes sont modélisés à l'aide de variables de décision et de contraintes, où une contrainte est une relation entre une ou plusieurs variables qui limite les valeurs que peuvent prendre simultanément chacune des variables liées par la contrainte. Les algorithmes de recherche de solution, en PPC, s'appuient généralement sur la propagation de contraintes, pour réduire le nombre de solutions candidates à explorer, ainsi que sur une recherche systématique parmi les différentes affectations possibles de chacune des variables. De tels algorithmes garantissent de trouver une solution, quand elle existe, et permettent de prouver qu'il n'existe pas de solution à un problème s'ils n'ont pas trouvé de solution à la fin de la recherche exhaustive.

Un des premiers solveur de contraintes est ALICE écrit en 1976 par Jean-Louis Laurière.

Problème de satisfaction de contraintes sur les domaines finis

Une contrainte est une relation entre plusieurs variables qui limitent l'ensemble des valeurs que peuvent prendre ces variables simultanément.

Définition — Un problème de satisfaction de contraintes sur des domaines finis (ou CSP) est défini par un triplet $({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ où:

• ${\mathcal {X}}=\{x_{1},\dots ,x_{n}\}$ est l'ensemble de variables du problème;
• ${\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}$ est l'ensemble des domaines des variables, c'est-à-dire que pour tout $k\in [1;n]$ on a $x_{k}\in {\mathcal {D}}_{k}$;
• ${\mathcal {C}}=\{C_{1},\dots ,C_{m}\}$ est un ensemble de contraintes. Une contrainte $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ est définie par l'ensemble ${\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}$ des variables sur lequel elle porte et la relation ${\mathcal {R}}_{i}\subset {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}$ qui définit l'ensemble des valeurs que peuvent prendre simultanément les variables de ${\mathcal {X}}_{i}$:

Lorsque l'on définit une contrainte en énumérant l'ensemble des valeurs qui satisfont cette contrainte, on dit que la contrainte est définie en extension. On trouve aussi d'autres représentations^{[réf. nécessaire]} de contraintes telles que:

• contraintes arithmétiques ($<,>,\leq ,\geq ,=,\neq$) sur des expressions ;
• contraintes logiques (disjonction, implication, etc.) ;
• contraintes dont la sémantique est décrite : « toutes différentes », etc.

On appelle affectation, le fait d'associer une valeur de son domaine à une variable. Dans le cadre de la résolution de problème de satisfaction de contraintes, on parle d'affectation partielle lorsque l'on affecte un sous-ensemble de l'ensemble des variables du problème, et d'affectation totale lorsque l'on affecte toutes les variables du problème.

Définition —  Une affectation ${\mathcal {A}}$ d'un CSP $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ est définie par le couple ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ où:

• ${\mathcal {X_{\mathcal {A}}}}\subset {\mathcal {X}}$ est un sous-ensemble de variables;
• ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ est le tuple des valeurs prises par les variables affectées.

On dit qu'une affectation est partielle lorsque l'ensemble de variables affectées est différent de l'ensemble des variables du problème, sinon on parle d'affectation totale.

Propriété — Soit ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ une affectation (partielle ou totale) d'un CSP $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$, et $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ une contrainte de $P$ telle que ${\mathcal {X}}_{i}\subset {\mathcal {X_{\mathcal {A}}}}$, l'affectation ${\mathcal {A}}$ satisfait la contrainte $C_{i}$ si et seulement si l'ensemble des valeurs ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ des variables sur lesquelles porte la contrainte $C_{i}$ appartient à ${\mathcal {R}}_{i}$.

Définition — Une solution d'un CSP est une affectation totale qui satisfait l'ensemble des contraintes.

Lors de la recherche de solutions à un problème de satisfaction de contraintes, on peut souhaiter par exemple :

• trouver une solution (satisfaisant l'ensemble des contraintes) ;
• trouver l'ensemble des solutions du problème ;
• trouver une solution optimale par rapport à un critère (généralement minimisation ou maximisation d'une variable) ;
• prouver la non existence de solution (dans le cas d'un problème sur-contraint).

Recherche de solutions

Recherche arborescente

Dans le cas de la résolution sur domaines finis, il est en théorie possible d'énumérer toutes les possibilités et de vérifier si elles violent ou non les contraintes, cette méthode est appelée générer et tester. Cependant, cela s'avère impraticable pour des problèmes de taille moyenne en raison du grand nombre de combinaisons possibles. Une des majeures parties de la résolution, appelée « filtrage », a pour but d'éviter cette énumération exhaustive. Elle consiste à déduire à partir des contraintes les valeurs impossibles. Lorsqu'une variable ne possède plus qu'un candidat, celle-ci est instanciée (i.e. cette valeur lui est affectée). Cependant, le filtrage seul ne permet pas d'instancier toutes les variables, et il est donc nécessaire de scinder le problème en plusieurs parties (par exemple en instanciant une variable à chacune de ses valeurs possibles) et relancer le filtrage sur l'une de ces parties et ce, de manière récursive jusqu'à obtenir l'instanciation de toutes les variables. Lorsque le filtrage détecte que l'instanciation partielle viole une contrainte, on utilise généralement alors un mécanisme de retour sur trace afin de remettre en cause le dernier choix effectué.

Cette série de découpages du problème peut être représentée sous forme d'un arbre. Le but de la recherche est de parcourir cet arbre (en le construisant au fur et à mesure) jusqu'à trouver une solution au problème tandis que le filtrage consiste à « élaguer » cet arbre en supprimant toutes les parties n'aboutissant qu'à des contradictions.

Propagation de contraintes

La propagation de contraintes (ou filtrage) consiste à supprimer d'un problème de PPC des valeurs de variables ne pouvant pas prendre part à une solution. Pour accélérer la recherche d'une solution d'un problème, il est nécessaire d'obtenir un bon compromis entre le temps nécessaire au filtrage et l'efficacité de celui-ci. C'est pourquoi il existe plusieurs niveaux d'efficacités de filtrage, capables de retirer plus ou moins de valeurs, pour un coût en temps plus ou moins élevé. Étant donné que toutes les contraintes d'un problème de PPC doivent être satisfaites, le fait pour une valeur d'une variable de ne pas pouvoir satisfaire une seule contrainte du problème implique qu'elle ne pourra prendre part à aucune solution du problème. Il est donc possible de raisonner séparément sur chaque contrainte afin de pouvoir trouver des valeurs pour lesquelles cette contrainte ne peut être satisfaite, et donc les retirer du problème entier.

On appelle consistance locale le fait de vérifier que certaines variables ne violent pas les contraintes qui lui sont liées. On ignore alors les autres variables et contraintes. Cela permet de filtrer alors certaines valeurs impossibles pour un coût réduit. Il existe plusieurs consistances locales, offrant chacune un équilibre différent entre efficacité du filtrage et rapidité de calcul.

Extensions

• contraintes valuées
• contraintes globales
• étude et détection des symétries
• techniques de décomposition et classes de problèmes « traitables »
• métaheuristiques
• transition de phase

Exemples de problèmes

Parmi les problèmes classiques pouvant être traités par programmation par contraintes, on peut citer :

• le problème des huit dames, qui consiste à placer huit dames sur un échiquier de manière qu'aucune dame ne puisse en prendre une autre ;
• le sudoku, où il faut remplir une grille 9x9 avec des chiffres de 1 à 9 de manière que chaque chiffre n'apparaisse qu'une seule fois dans chaque ligne, colonne, et sous-boîte de taille 3x3.

Solveurs de contraintes

• Logiciels académiques
  • Prolog III (1989)
  • MiniCP (Bibliothèque Java destinée à l'enseignement de la programmation par contraintes. License Libre) (2018)
• Logiciels commerciaux
  • Artelys Kalis (Bibliothèques C++, Java, Python, module de la suite FICO Xpress)
  • CHIP V5 (C, C++, Prolog) (1988)
  • Comet (Langage orienté objet destiné à la résolution de problèmes de contraintes. Usage académique libre.)
  • Disolver (Bibliothèque C++)
  • IBM CP Optimizer, successeur de ILOG Solver/Scheduler (Bibliothèques C++, Python, Java, .NET)
  • Prolog IV (1996)
• Logiciels sous licences libres
  • AbsCon (Bibliothèque Java)
  • Choco (Bibliothèque Java, logiciel libre : X11 style)
  • Cream (Bibliothèque Java)
  • Eclipse Prolog (Bibliothèque Prolog)
  • Gecode (Bibliothèque C++)
  • Google OR-tools (Bibliothèque C++, bindings Java, C#, Python)
  • JaCoP (Bibliothèque Java)
  • JOpt (Bibliothèque Java)
  • Minion (C++)
  • OscaR (Scala)
  • Scarab (Bibliothèque Scala)
  • python-constraint (Bibliothèque Python)

Bibliographie

• (en) Thom Frühwirth et Slim Abdennadher, Essentials of Constraint Programming, Springer, avril 2003, 145 p. [détail des éditions] (ISBN 978-3-540-67623-2, présentation en ligne)
• (en) Francesca Rossi, Peter Van Beek et Toby Walsh, Handbook of constraint programming, Elsevier, 2006 [détail des éditions] (ISBN 978-0-444-52726-4, présentation en ligne)
• Annick Fron, Programmation par Contraintes, The Book Edition, (ISBN 978-2879080628)
• (en)Trends in Constraint Programming, edited by Frédéric Benhamou, Narendra Jussien, Barry O’Sullivan, © ISTE Ltd, 2007 (ISBN 978-1-905-209-97-2)

Voir aussi

Articles connexes

• Problème de satisfaction de contrainte
• Programmation logique

Liens externes

• AFPC : Association française de programmation par contraintes
• Article sur l'utilisation du sudoku comme outil pédagogique pour la PPC
• (en) Global Constraint Catalog : catalogue de contraintes globales (N. Beldiceanu)