Programmation par contraintes
La Programmation par contraintes (PPC) permet de résoudre des problèmes de type Satisfaction de Contraintes (CSP). Un CSP est un problème modélisation sous la forme d’un ensemble de contraintes posées sur des variables, chacune de ces variables prenant ses valeurs dans un domaine défini.
Un CSP est défini par un triplet (X,D,C,R) tel que :
- X={X1,X2,…,Xn} l’ensemble des variables du problème;
- D une fonction qui associe à chaque variable Xi son domaine (ensemble de valeurs possibles) D(Xi);
- C=C1,C2,…,Ck} l’ensemble des contraintes.
Solution par Programmation par contraintes
Résoudre un CSP consiste à affecter des valeurs aux variables, de telle sorte que toutes les contraintes soient satisfaites. Pour cela, nous avons besoin d’un vocabulaire précis :
- Une affectation est une instance de certaines variables par des valeurs de leurs domaines respectifs. On notera A={(X1,V1),…} affectation qui instancie la variable X1 par la valeur V1, etc;
- Une affectation est dite totale si elle instancie toutes les variables du problème, sinon elle est dite partielle;
- Une affectation A viole une contrainte Ck si toutes les variables de Ck sont instanciées dans A et si la relation définie par Ck n’est pas vérifiée par l’affectation:
- Une affectation totale ou partielle est consistante si elle ne viole aucune contrainte, sinon elle est dite inconsistante;
- Une solution du CSP est une affectation totale consistante.
Dans la programmation par contraintes, lorsqu’un CSP n’a pas de solution, on dit qu’il est surcontraint. Dans ce cas, on peut trouver l’affectation totale qui viole le moins de contraintes possibles. On parle alors de max-CSP.
Une autre possibilité dans la programmation par contraintes est d’affecter un poids à chaque contrainte, on cherche alors à minimiser le poids des contraintes violées. On parle alors de VCSP (valued). Un max-CSP est un VCSP où toutes les contraintes ont le même poids.
Lorsqu’un CSP admet plusieurs solutions différentes, on dit qu’il est sous-contraint. Si les solutions ne sont pas toutes équivalentes, alors il est possible d’établir des préférences entre les solutions. On ajoute une fonction qui associe une valeur numérique à chaque solution, représentant la qualité de cette solution. L’objectif est de maximiser cette fonction objectif. On parle alors de CSOP (constraint satisfaction optimisation problem).
Exemple de Programmation par contraintes : problème des n-reines
Un constructeur possède un terrain possédant 16 parcelles (4 lignes et 4 colonnes) formant un échiquier. Il souhaite disposer des éoliennes de telle façon qu’ils ne soient pas en prise. Deux éoliennes sont en prise s’ils se trouvent sur la même ligne, la même colonne ou une même diagonale.
Programmation par contraintes 1
Les variables sont les positions lignes et colonnes des éoliennes sur l’échiquier. On associe à chaque éolienne i deux variables Li et Ci correspondant respectivement à la ligne et la colonne sur laquelle placer l’éolienne. Nous avons la modélisation de la programmation par contraintes suivante :
- Variables :
- X={L1, L2, L3, L4, C1, C2, C3, C4}
- Domaines :
- D(L1)=D(L2)=D(L3)=D(L4)={1,2,3,4}
- D(C1)=D(C2)=D(C3)=D(C4)={1,2,3,4}
- Contraintes :
- Clig = allDiff({L1, L2, L3, L4}) pour avoir des valeurs Li toutes différentes les unes des autres
- Ccol = allDiff({C1, C2, C3, C4}) pour avoir des valeurs Ci toutes différentes les unes des autres
- Cdm={Ci+Li != Cj+Lj / pour tout i et j dans {1,2,3,4} et i != j}
- Cdd={Ci-Li != Cj-Lj / pour tout i et j dans {1,2,3,4} et i != j}
- C est l’union de ces ensemble.
Cette modélisation est naïve puisque l’on considère toutes les contraintes sans en chercher leur signification.
Programmation par contraintes 2
Il est facile de remarquer qu’il y aura minimum une éolienne par colonne de l’échiquier (ou ligne etc). La programmation par contraintes consiste alors à déterminer sur quelle ligne se trouve l’éolienne placée sur la colonne i, la variable sera notée Xi :
- Variables :
- X={X1, X2, X3, X4}
- Domaines :
- D(X1)=D(X2)=D(X3)=D(X4)={1,2,3,4}
- Contraintes :
- Clig = allDiff({X1, X2, X3, X4}) pour avoir des valeurs Xi toutes différentes les unes des autres
- Cdm={Xi+i != Xj+j / pour tout i et j dans {1,2,3,4} et i != j}
- Cdd={Xi-i != Xj-j / pour tout i et j dans {1,2,3,4} et i != j}
- C est l’union de ces ensemble.
Discussion
Il existe bien d’autres façon de modéliser le problème. Dans ce cas, quelle est la meilleure modélisation ? Pour cela, il y a trois critères permettant d’évaluer la pertinence de la modélisation : modélise-t-elle le mieux le problème ? la modélisation a-t-elle été triviale ? la modélisation permet-elle de résoudre le problème efficacement ?
Résolution d’un CSP
La résolution d’un CSP est un problème Np-Complet dans le cas général. Le mécanisme de résolution consiste à répéter les deux étapes suivantes :
- réduction des problèmes par filtrage;
- parcours de l’arbre de recherche.
Ces deux étapes font appel à des notions telles que la consistance d’arcs ou la propagation de contraintes que nous ne développerons pas dans ce cours. Il existe de très nombreux solveurs d’un CSP comme par exemple la bibliothèque Google OR-tools.
