Voir la source de Programmation par contraintes

La '''programmation par contraintes''' (PPC, ou CP pour ''constraint programming'' en anglais) est un [[Paradigme (programmation)|paradigme de programmation]] apparu dans les années 1970 et 1980<ref>Mackworth, Consistency in networks of relations, ''Artificial Intelligence'', 9:99-118, 1977</ref>{{,}}<ref>Haralick, Eliott, Increasing Tree search efficiency for Constraint Satisfaction Problems, ''Artificial Intelligence'', 14:263-313, 1980</ref> permettant de résoudre des problèmes combinatoires de grande taille tels que les problèmes de planification et d'ordonnancement<ref>Roman Bartak, A Guide to Constraint Programming, 1998</ref>. 

En programmation par contraintes, on sépare la partie modélisation à l'aide de ''[[problème de satisfaction de contraintes|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]]).

{{Citation bloc|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<ref>E. Freuder. "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."</ref>}}

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]]<ref>{{Ouvrage
 | prénom1                = Jean-Louis
 | nom1                   = Laurière
 | titre                  = Un langage et un programme pour énoncer et résoudre des problèmes combinatoires
 | éditeur                = Thèse d'Etat, Université Pierre et Marie Curie
 | lieu                   = Paris
 | année                  = 1976
 | pages totales          = 227
 | isbn                   = 
 
 | sudoc                  = 029557313
}}</ref>{{,}}<ref>
{{Article
 | langue                 = anglais
 | prénom1                = Jean-Louis
 | nom1                   = Laurière
 | titre                  = A language and a program for stating and solving combinatorial problems
 | périodique             = Artificial Intelligence
 | volume                 = 10
 | numéro                 = 1
 | mois                   = février
 | date                   = 1978
 | pages                  = 29-127
 | consulté le            = 7 janvier 2018 
 | lire en ligne          = http://www.sciencedirect.com/science/article/pii/0004370278900292
}}</ref>{{,}}<ref>{{Lien web
 | langue           = anglais
 | auteur1          = Pierre Flener
 | url              = http://school.a4cp.org/summer2017/slidedecks/NutCPshell.pdf
 | titre            = Constraint Programming in a Nutshell
 | série            = Joint ACP and GdR RO Summer School 2017
 | jour             = 18-19
 | mois             = 09
 | année            = 2017
 | site             = lien
 | consulté le      = 7 janvier 2018
 }}.</ref>.

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

{{Théorème
|Définition
|Un problème de satisfaction de contraintes sur des domaines finis (ou CSP) est défini par un triplet <math>(\mathcal{X},\mathcal{D},\mathcal{C})</math> où:
* <math>\mathcal{X} = \{x_1, \dots, x_n \}</math> est l'ensemble de variables du problème;
* <math>\mathcal{D} = \{\mathcal{D}_1, \dots, \mathcal{D}_n \}</math> est l'ensemble des domaines des variables, c'est-à-dire que pour tout <math>k \in [1; n]</math> on a <math>x_k \in \mathcal{D}_k</math>;
* <math>\mathcal{C} = \{C_1, \dots, C_m \}</math> est un ensemble de contraintes. Une contrainte <math>C_i=(\mathcal{X}_i, \mathcal{R}_i)</math> est définie par l'ensemble <math>\mathcal{X}_i = \{x_{i_1}, \dots, x_{i_k}\}</math> des variables sur lequel elle porte et la relation <math>\mathcal{R}_i \subset \mathcal{D}_{i_1} \times \dots \times \mathcal{D}_{i_k}</math> qui définit l'ensemble des valeurs que peuvent prendre simultanément les variables de <math>\mathcal{X}_i</math>:
}}

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{{ref nec}} de contraintes telles que:

* contraintes arithmétiques (<math><, >, \leq, \geq, =, \neq</math>) 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.

{{Théorème
|Définition
| Une affectation <math>\mathcal{A}</math> d'un CSP <math>P = (\mathcal{X},\mathcal{D},\mathcal{C})</math>  est définie par le couple <math>\mathcal{A} = (\mathcal{X_{\mathcal{A}}}, \mathcal{V_{\mathcal{A}}})</math> où:
* <math>\mathcal{X_{\mathcal{A}}} \subset \mathcal{X} </math> est un sous-ensemble de variables;
* <math>\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}\}</math> 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.

{{Théorème
|Propriété
|Soit <math>\mathcal{A} = (\mathcal{X_{\mathcal{A}}}, \mathcal{V_{\mathcal{A}}})</math> une affectation (partielle ou totale) d'un CSP <math>P = (\mathcal{X},\mathcal{D},\mathcal{C})</math>, et <math>C_i = (\mathcal{X}_i, \mathcal{R}_i)</math> une contrainte de <math>P</math> telle que <math>\mathcal{X}_i \subset \mathcal{X_{\mathcal{A}}}</math>, l'affectation <math>\mathcal{A}</math> satisfait la contrainte <math>C_i</math>  si et seulement si l'ensemble des valeurs <math>\mathcal{V}_{\mathcal{A}_i} = \{ v_i \in \mathcal{V}_{\mathcal{A}} \mbox{ tel que } x_i \in \mathcal{X}_{i} \}</math> des variables sur lesquelles porte la contrainte <math>C_i</math> appartient à <math>\mathcal{R}_i</math>.
}}

{{Théorème
|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 (mathématiques)|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.

=== Extensions ===
* contraintes valuées
* contraintes globales<ref name="NBEC94">[http://www.sciencedirect.com/science/article/pii/0895717794901279 Introducing global constraints in CHIP] N.Beldiceanu, E.Contejean, Mathematical and Computer Modelling, December 1994, Elsevier</ref> 
* é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 {{nobr|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 (programming language)|Java]] destinée à l'enseignement de la programmation par contraintes. License Libre) (2018)<ref>{{Lien web|titre=www.minicp.org|url=http://www.minicp.org/|site=minicp.org|consulté le=2019-10-04}}.</ref>
* Logiciels commerciaux
** Artelys Kalis (Bibliothèques [[C++]], [[Java (programming language)|Java]], [[Python (langage)|Python]], module de la suite FICO Xpress)
** CHIP V5 ([[C (langage)|C]], [[C++]], Prolog) (1988) <ref>The constraint logic programming language CHIP, Proceedings of international conference on Fifth Generation Computer Systems FGCS-88 (1988), pp. 693–702</ref>{{,}}<ref name="NBEC94"/>
** Comet  (Langage orienté objet destiné à la résolution de problèmes de contraintes. Usage académique libre.)
** Disolver (Bibliothèque [[C++]])
** [[IBM]] CP Optimizer<ref>{{Lien web |url= http://www.ibm.com/analytics/cplex-cp-optimizer/ |titre= IBM ILOG CP Optimizer|langue=en |site=ibm.com}}.</ref>{{,}}<ref name="CPOptimizer20182">{{article|auteurs=Laborie P, Rogerie J, Shaw P, Vilim P|date=2018|titre=IBM ILOG CP optimizer for scheduling|journal=Constraints|volume=23|numéro=2|pages=210–250|doi=10.1007/s10601-018-9281-x}}</ref>, successeur de ILOG Solver/Scheduler (Bibliothèques [[C++]], Python<ref>{{Lien web |url= https://pypi.python.org/pypi/docplex |titre=docplex 2.10.154 |langue=en |site=python.org}}.</ref>, [[Java (programming language)|Java]], [[.NET]])
** Prolog IV (1996)
* Logiciels sous licences libres
** AbsCon (Bibliothèque [[Java (programming language)|Java]])
** Choco (Bibliothèque [[Java (programming language)|Java]], [[logiciel libre]] : X11 style)
** Cream (Bibliothèque [[Java (programming language)|Java]])
** Eclipse Prolog (Bibliothèque Prolog)
** Gecode (Bibliothèque [[C++]])
** [[Google]] OR-tools (Bibliothèque [[C++]], bindings [[Java (programming language)|Java]], [[C sharp|C#]], [[Python (langage)|Python]])
** JaCoP (Bibliothèque [[Java (programming language)|Java]])
** JOpt (Bibliothèque [[Java (programming language)|Java]])
** Minion ([[C++]])
** NuCS (Bibliothèque [[Python (langage)|Python]])
**OscaR ([[Scala (langage)|Scala]])
** Scarab (Bibliothèque [[Scala (langage)|Scala]])
** python-constraint (Bibliothèque [[Python (langage)|Python]])

== Bibliographie ==
* {{Essentials of Constraint Programming}}
* {{Handbook of constraint programming}}
* 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  <ref>[http://onlinelibrary.wiley.com/doi/10.1002/9780470612309.fmatter/pdf Trends in Constraint Programming]</ref> {{ISBN|978-1-905-209-97-2}}

== Notes et références ==
{{Références}}

== Voir aussi ==
=== Articles connexes ===
* [[Problème de satisfaction de contrainte]]
* [[Programmation logique]]

=== Liens externes ===
* [http://www.afpc-asso.org AFPC] : Association française de programmation par contraintes
* [http://www.e-tud.com/une/?11-narendra-jussien-introduit-le-sudoku-dans-une-ecole-d-ingenieur Article sur l'utilisation du sudoku comme outil pédagogique pour la PPC]
* {{en}} [http://www.emn.fr/x-info/sdemasse/gccat/index.html Global Constraint Catalog] : catalogue de contraintes globales (N. Beldiceanu)

{{Palette|Paradigme de programmation}}
{{Portail|Informatique théorique|programmation informatique}}

[[Catégorie:Algorithmique]]
[[Catégorie:Recherche opérationnelle]]
[[Catégorie:Paradigme de programmation|Contraintes]]
[[Catégorie:Langage de programmation logique]]
[[Catégorie:Optimisation combinatoire]]