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 1980^[1],[2] permettant de résoudre des problèmes combinatoires de grandes tailles tels que les problèmes de planification et d'ordonnancement^[3]. En programmation par contraintes, on sépare la partie modélisation à l'aide de problème 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).

« Constraint Programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it. »

— E. Freuder

Dans le cadre de la PPC, 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 affectation possible 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 CSP s'ils n'ont pas trouvé de solutions à la fin de la recherche exhaustive.

Le premier solveur de contraintes publié est une extension de Prolog écrite par Jaffar et Lassez en 1987.

Problème de satisfaction de contraintes sur les domaines finis

Article détaillé : Problème de satisfaction de contraintes.

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 contraintes $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éfinie 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 tel 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

Article détaillé : 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.

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 à ce qu'aucune dame ne puisse en prendre une autre;
• le sudoku, où il faut remplir une grille 9x9 avec des chiffres de 1 à 9 tel que chaque chiffre n'apparaisse qu'une seul fois dans chaque ligne, colonne, et sous-boîte de taille 3x3;

Solveurs de contraintes

• Logiciel propriétaire
  • Artelys Kalis (C++, bibliothèques Java)
  • Comet (Langage orienté objet dédié à la résolution de problèmes de contraintes. Gratuiciel pour usage académique.)
  • Disolver (Bibliothèque C++)
  • ILOG CP Optimizer et ILOG CP (bibliothèques C++, Java, .Net)
  • Koalog Constraint Solver (Bibliothèque Java)
• Logiciel libre
  • Eclipse Prolog (Bibliothèque Prolog)
  • Choco (Bibliothèque Java, logiciel libre : X11 style)
  • Gecode (Bibliothèque C++)
  • JOpt (Bibliothèque Java)
  • JaCoP (Bibliothèque Java)
  • Minion (C++)
  • python-constraint (Bibliothèque Python)
  • Cream (Bibliothèque Java)

Extensions

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

Notes et références

1. ↑ Mackworth, Consistency in networks of relations, Artificial Intelligence, 9:99-118, 1977
2. ↑ Haralick, Eliott, Increasing Tree search efficiency for Constraint Satisfaction Problems, Artificial Intelligence, 14:263-313, 1980
3. ↑ Roman Bartak, A Guide to Constraint Programming, 1998

Bibliographie

• (en) Thom Frühwirth et Slim Abdennadher, Essentials of Constraint Programming, Springer, avril 2003, 145 p. (ISBN 978-3-540-67623-2) [présentation en ligne] 

Voir aussi

Articles connexes

• Problème de satisfaction de contrainte
• Programmation logique

Liens et documents 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 riche et documenté.