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è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).

« 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 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 par Jean-Louis Laurière et publié en 1978 dans Artificial Intelligence, 10(1) p. 29-127.^{[réf. nécessaire]}.

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 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

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 seule fois dans chaque ligne, colonne, et sous-boîte de taille 3x3;

Solveurs de contraintes

Le ton de cet article ou de cette section est trop promotionnel ou publicitaire.

Modifiez l'article pour adopter un ton neutre (aide quant au style) ou discutez-en.

Logiciel propriétaire
- Artelys Kalis (Bibliothèques C++, Java, Python, module de la suite FICO Xpress)
- CHIP V5 (C, C++, Prolog)
- Comet (Langage orienté objet dédié à la résolution de problèmes de contraintes. Gratuiciel pour usage académique.)
- Disolver (Bibliothèque C++)
- IBM CP Optimizer, anciennement ILOG CP Optimizer (Bibilothèques C++, Java, .NET)
- Jekejeke Minlog (Bibliothèque Prolog)
Logiciel libre
- 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++)
- Scarab (Bibliothèque Scala)
- python-constraint (Bibliothèque Python)

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

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

Annick Fron, Programmation par Contraintes, The Book Edition, (ISBN 978-918417-00-2)^{[à vérifier : La longueur du numéro ISBN devrait être 10 ou 13 et non 12, demandé le 22 septembre 2013]}

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)

Voir aussi

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

Portail de l'informatique théorique
Portail de la programmation informatique

This article is issued from Wikipédia - version of the Monday, October 26, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.