Programmation par contraintes

La PPC permet de résoudre des problèmes décisionnels. Un problème d’optimisation se résout successivement après plusieurs problèmes de décision. Par exemple pour déterminer un plus court chemin, nous chercherons a trouver un chemin de moins de 100 (possible), puis moins de 50 (impossible), puis moins de 75, etc. jusqu’à trouver la solution optimale. La PPC a un champ d’action plus large que les méthodes exactes ou les méta-heuristiques.

Définition

La PPC résout un problème de satisfaction de contraintes (CSP).

Ce dernier est défini par un triplet <X,D,C> avec X l’ensemble de variables, D l’ensemble de domaines et C l’ensemble de contraintes. Le Domaine Di est l’ensemble des valeurs possibles pour la variable Xi. Chaque contraintes Cj se définit par son arité (le nombre de variable sur lesquelles elle porte), la liste de ces variables et l’ensemble des tuples qui la satisfont.

Prenons un exemple de triplet :

  • variables : A, B, C, D
  • domaines :
    • DA = {1,4,5,8}
    • DB = {2,3,5,7,9}
    • DC = {4,8,9}
    • DD = {1,4,5,7,9}
  • contraintes :
    • C1(A,C) : {(1,7); (1,9); (5,9); (8,9)}
    • C2(A,D) : (1,1);(1,5);(5,5);(5,9);(8,9)}
    • C3(C,D) : {(4,1);(8,1);(9,7)}
    • C4(B,D) : {(2,7);(2,9);(5,8);(7,9);(9,9)}

Il est possible de coder les contraintes en extension, par un ensemble de tuples, ou en intention, en utilisant des opérateurs dont la sémantique est connue. Une instanciation est une affectation complète de valeurs aux variables, par exemple {<A,1>,<B,7>,<C,4>,<D,9>}. L’instanciation est une solution valide si les valeurs données aux variables dont telles que toutes les contraintes sont vérifiées.

On parle d’instanciation partielle ou totale (si elle prend toutes les variables ou non), et inconsistante ou consistante (si elle valide les contraintes ou non). Une solution valide est donc une instanciation totale et consistante.

Résolution naïve : Generate & Test

On génère toutes les affectations possibles. Puis on vérifie si elles sont consistantes, dès qu’une affectation est consistante nous avons une solution valide.

Si on a un problème à n variables, chacune ne peut prendre que deux valeurs, le processeur fait 1000000000 calcul à la seconde. Pour 30 variables, la résolution prendre au plus 1s, pour 50 variables, on passe à 11 jours; pour 70 variables il faut attendre 317 siècles.

Résolution par backtrack

On génère l’arbre des affectations puis on le parcours en profondeur. Si une affectation partielle (durant le parcours) est inconsistante, alors on coupe le sous-arbre correspondant.

Cela s’apparente à du Branch&Cut.

ppc1

Cette méthode ne génère pas l’arbre des possibilités en entier contrairement à la méthode naïve. Par contre toutes les contraintes sont testées à chaque affectation partielle et le temps de convergence dépend aussi de l’ordre des variables.

Résolution par propagation de contraintes

Cette méthode consiste à propager les contraintes dans le domaine des variables.

Par exemple prenons x entre 0 et 10 et y entre 3 et 9; alors avec la contrainte x>y nous pouvons restreindre le domaine de X entre 4 et 10.

ppc2

Il existe trois cas où l’on propage l’information :

  • quand un domaine est réduit
  • quand une des bornes du domaine est changée
  • quand un domaine est un singleton.

Il est alors possible de propager l’information une fois (noeud-consistance), deux fois (arc-consistance) ou plus.

Dans le noeud-consistance, pour chaque variable Xi non affectée dans A, on enlève de DXi toute valeur v telle que l’affectation A ∪{(Xi,v)} est inconsistante. On propage les valeurs autorisées en profondeur.

ppc3

Dans l’arc-consistance, pour chaque variable Xi non affecté dans A, on enlève de DXi toute valeur v telle qu’il existe une variable Xj non affectée pour laquelle, pour toute valeur w de DXj, l’affectation A ∪{(Xi,v);(Xj,w)} soit inconsistante. On propage les valeurs autorisées en profondeur.

ppc4

Plus le tuple de comparaison est grand, plus le temps de calcul pour définir le domaine valide des variables est grand. L’arc-consistance se révèle moins efficace que le noeud-consistance si les domaines sont grands.

Publicités