Programmation par contraintes - Définition

Présentation

La programmation par contraintes (PPC, ou Constraint Programming (CP) en anglais) consiste à programmer avec des relations appelées 'contraintes'. Un problème comporte un certain nombre de variables, chacune ayant un domaine, et un certain nombre de contraintes. Une contrainte implique une ou plusieurs variables, et restreint les valeurs que peuvent prendre simultanément ces variables. Trouver une solution à un problème de PPC consiste à décrire l'ensemble des affectations autorisées de chaque variable, de telle sorte que la totalité des contraintes soient satisfaites.

• Définition
• Historique
• Tout ce que vous devez savoir sur la PPC en moins de 5 mn

Programmation par Contraintes sur les domaines finis

Description du problème de satisfaction de contraintes

Un problème comporte un certain nombre de variables, chacune ayant un domaine fini, et un certain nombre de contraintes.

Une contrainte implique une ou plusieurs variables, en définissant les combinaisons autorisées et celles qui sont interdites. Lorsqu'une contrainte implique deux variables, on parle de contrainte binaire. Lorsqu'elle implique un nombre non fixé de variables, on parle de contrainte globale.

Trouver une solution à un problème de PPC consiste à affecter une valeur à chaque variable, de telle sorte que la totalité des contraintes soient satisfaites. Il serait possible d'énumérer toutes les possibilités et vérifier si elles violent ou non les contraintes. Cependant cela serait extrèmement lourd en calcul. La partie la plus importante est appelée "filtrage", 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. Cependant le filtrage ne permet pas toujours d'instancier toutes les variables. Il faut alors faire des choix arbitraire puis recommencer le filtrage. Si ce choix mène à une contradiction, on annule le choix arbitraire par backtracking.

Algorithmes de recherche : en profondeur, en largeur, heuristiques, LDS

Consistances locales

La consistance locale consiste à vérifier que certaines variables ne violent pas les contraintes liées à cette variable. On ignore alors les autres variables et contraintes. Cela permet de filtrer certaines valeurs impossibles, cependant il sera impossible d'avoir un filtrage parfait, puisqu'on ignore alors certaines contraintes.

Consistance de nœud

Elle consiste à ne considérer qu'une seule variable. Cependant les contraintes portent généralement sur au moins deux variables. Cette consistence n'apporte donc que peu d'informations.

Consistance d'arc

Aussi appelée Arc Consistency (AC), il s'agit de la méthode la plus employée. Elle s'applique dans le cas de contraintes binaires (i.e. impliquant deux variables). Une contrainte binaire peut être représentée par un arc reliant les deux variables impliquées, d'où l'emploi du mot arc. Une contrainte satisfait la consistance d'arc si chaque valeur de chaque variable appartient à une solution de la contrainte. On établit la consistance d'arc en supprimant les valeurs qui ne satisfont pas cette propriété.

Par exemple, soient V₁ ∈ [1,2,3] et V₂ ∈ [1,3] avec la contrainte V₁ = V₂. On a alors les solutions 1-1 et 3-3. La valeur 2 de V₁ n'appartenant pas à une solution, on la supprime du domaine.

Consistance d'hyperarc

Aussi appelée Hyperarc Consistency (HAC), c'est une généralisation de la consistance d'arc pour les contraintes non binaires. Son nom vient du fait que les variables impliquées peuvent être reliées par un hyperarc (nom d'un arc dans un hypergraphe). Elle a aussi été appelée consistance d'arc généralisée. Le principe est le même que pour les contraintes binaires : une contrainte est HAC si et seulement si chaque valeur de chaque variable appartient à une solution de la contrainte. On établit la consistance d'hyperarc en supprimant toutes les valeurs qui ne satisfont pas cette propriété.

Par exemple, la contrainte Alldiff impliquent que les variables sur lesquelles elle est définie prennent des valeurs deux à deux différentes. On sait établir efficacement la consistance d'hyperarc pour cette contrainte.

k-consistance

Elle consiste à considérer k variables, et de tester tous les k-uplets de valeurs possibles afin de tester s'ils ne violent pas les contraintes. Plus k est grand, plus le filtrage sera efficace. Cependant, du fait du grand nombre de combinaisons à tester, cela reste souvent trop lourd. La 3-consistence donne de bons résultats, cependant du fait de la complexité de son implémentation, elle n'est que très rarement présente dans des solveurs de contraintes.

La 2-consistence est en fait la consistance d'arc. Si un problème contient n variables, alors la n-consistance consisterait à tester l'ensemble des possibilités.

Chemin

Consistance de bornes

Lorsque les domaines des variables sont trop grands (plusieurs milliers d'élements), l'énumération de toutes les possibilités devient alors trop lourd. On ne travaille alors plus que sur les bornes inférieures et supérieures du domaine. Cela fonctionne très bien avec certaines contraintes comme <, > ou =.

Algorithmes de consistance locale

AC1, AC2, AC3, AC4, AC5, AC6, AC7, AC8, AC2001

Exemples

N-Dames

Le problème des N-Dames consiste à placer N dames sur un échiquier NxN sans que l'une d'elles puisse en manger une autre (avec les règles des échecs : une dame peut " manger " toute pièce située sur sa ligne, sur sa colonne ou sur l'une de ses deux diagonales). Pour plus de détails sur ce problème, voir le Problème des huit dames.

Le problème peut être représenté avec N variables (V_i ∈ [1..N], i=1 .. N), représentant la position en colonne de la dame de la ligne i. En effet, comme deux dames ne peuvent pas être sur la même ligne, et qu'il y a autant de dames que de lignes, il y a exactement une et une seule dame par ligne.

Les contraintes imposées sur les variables V_i sont :

pour tout i ≠ j :

• V_i ≠ V_j (ne pas mettre deux dames sur la même colonne).
• V_i - i ≠ V_j - j (ne pas mettre deux dames sur la même diagonale NO-SE)
• V_i + i ≠ V_j + j (ne pas mettre deux dame sur la même diagonale NE-SO)

send+more=money

Soit l'équation :

send
+more
-----
money

Le but est d'associer un chiffre à chaque lettre tel que la somme soit vérifie. Les variables sont donc s,e,n,d,m,o,r et y toutes étant des entiers dans [0,9]. On pose la contrainte .

Sudoku

Le sudoku consiste à 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.

Les variables sont donc naturellement des entiers dans [1,9]. On utilise ensuite la contrainte globale AllDifferent qui est bien connue sur chaque ligne, colonne, et sous-boîte.

Autres

reconnaissance de scènes 3D, raisonnement temporel qualitatif

Applications

La PPC se révèle très efficace pour des problèmes d'emploi du temps et d'affectation, de ce fait elle est principalement utilisée dans le cadre de problèmes de logistique complexes.

Autres domaines de contraintes

• termes
• booléens
• réels
• intervalles
• ensembles
• chaînes

Solveurs de contraintes

• Etude théorique
• Architecture d'un solveur
• Langages d'expression des propagateurs: indexicaux, CHRs
• liens vers solveurs libres et commerciaux

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