PPC > Notions de bases > Le C.S.P

Qu'est-ce qu'un C.S.P ?

Un CSP (Constraints Satisfaction Problem) se décrit par un ensemble de variables (au sens « inconnues ») dont le domaine est souvent discret (entier, ensemble, booléen) et un ensemble de contraintes sur ces variables. La résolution consiste alors à trouver un tuple de valeurs tel que toutes les contraintes soient satisfaites.

Un C.S.P. peut donc se décrire ainsi :

  • X = { X1, X2, ..., Xn}
  • X1 D1, X2 D2, ... Xn Dn
  • C = {C1, C2, ..., Ck}

Les variables : Dans un CSP, les domaines sont discrets et finis. On a donc soit un intervalle de valeurs (Par exemple : X ∈ [[ 0,17 ]] ), soit un ensemble discontinus de valeurs (Par exemple : {1,4,8,13} ). Ceci donne donc naissance à deux types de variables : les Variables sur les Bornes ( on ne stocke que les bornes actuelles du domaine ) et les Variables Enumérées : on stocke une à une les valeurs.

Les Contraintes

Les contraintes sont des relations sur les variables. Par exemple si x = [[ 1,2 ]] et y = [[1,2]], la contrainte x != y peut être décrite par la relation { (1,2) , (2,1) }. Pour plusieurs raisons, les solveurs sont fournis avec des contraintes par défaut. Par exemple, dans le solveur libre Choco, on retrouve :

  • Des contraintes arithmétiques (=, <, >, >=…) sur des combinaisons linéaires
  • Des contraintes sémantiques :
    • allDifferent : elle permet de choisir des valeurs toutes différentes pour chaque variable
      Ex : allDifferent( { x1, x2, x3, x4 } )
    • occurrence : elle permet de contraindre le nombre d’occurrences d’une valeur
      Ex : occurrence( occ, 7, { x1, x2 } )
    • element : elle permet de choisir une valeur dans un tableau
      Ex : element( val, idx, ( 1,3,4,2 ) ) => val = (1,3,4,2) [idx]

  • Des contraintes en extension où l’on fournit les tuples autorisés
  • Des meta-contraintes logiques : implication, disjonction…

L’Arité des contraintes

Une contrainte peut avoir une arité quelconque :

  • Une contrainte est dite unaire si elle porte sur une seule variable (x=4).
  • Une contrainte binaire comprend deux variables (x+y=9).
  • Une contrainte n-aire comprend n variables.

On utilise couramment le qualificatif « n-aire » pour une contrainte dont le nombre de variables n’est pas fixé à l’avance (Comme par exemple occurrence, allDifferent…).

Les Solutions

Un tuple ou une affectation est une liste de valeurs choisies pour chacune de variables du problèmes (ou un sous-ensemble dans le cas d’une affectation partielle lors d’une recherche). Un tuple viole une contrainte si ses valeurs n’appartiennent pas à la relation. Il est dit consistant s’il ne viole aucune contrainte. Une affectation est dite totale si elle instancie toutes les variables du problème et partielle si elle n'en instancie qu'une partie.

Une solution à un C.S.P est un tuple sur l’ensemble des variables qui est consistant. Un problème peut être sous-contraint (s'il y a plusieurs solutions possibles) ou sur-contraint (s'il n'y a pas de solution)

La programmation par contraintes résout un CSP de manière déclarative (l’utilisateur ne fournit que le modèle). Dans l’idéal, on a donc la modélisation à la charge de l’utilisateur et la résolution à la charge du solveur. Il est donc primordial de savoir modéliser un problème.

La Recherche

Afin de trouver une solution à un CSP, on va devoir implémenter une stratégie de recherche. Cette stratégie se base sur 2 choix simultanés : le choix des variables et le choix des valeurs.

  • Le choix des variables

    Pour faire des choix dans la recherche, il faut choisir la variable que l’on va essayer de modifier. Une solution simple consiste à utiliser une liste (ordonnée) de variables fournie par le problème (ordre d’ajout des variables par exemple) ou fournie par l’utilisateur (en fonction de l’importance d’une variable dans le problème). Il s’agit d’une heuristique statique (planifiée en dehors de la résolution)

    Le but est d’explorer au minimum. On peut soit commencer par les variables avec le moins de valeurs possibles (« MinDomain »), soit commencer par les variables les plus contraintes (« MaxConstrained »). L’heuristique la plus utilisée : « Dom over deg » s’inspire des deux. On prend la variable ayant le rapport « Taille domaine / Nombre contraintes » le plus petit

    L'utilisateur, qui connaît bien son problème, peut décider de d'une heuristique personnalisée de branchement qui prend en compte sa sémantique. Par exemple, si on minimise, on souhaite prendre les variables qui ont le plus d’impact sur l’objectif. Si des variables ont des rôles différents, on peut souhaiter sélectionner en priorité aux variables intervenants dans un nombre important de contraintes ou ayant un impact élevé dans la fonction objectif.

    Pour aller plus loin (des recherches sont menées actuellement dans ce domaine), on peut s’inspirer du passé de la recherche de solutions et prendre des choix qui ont déjà amené une contradiction dans les branches précédentes pour accélérer la recherche. L'utilisation d'explications d'échecs peut permettre de faire remonter des erreurs à ne pas reproduire.

  • Le choix des valeurs

    Si on a aucune connaissance sur la sémantique des valeurs, il est difficile de choisir. Il existe donc heuristique par défaut comme le Choix incrémental des valeurs ou le Choix inverse. Pour les grands domaines, il est inconcevable d’essayer toutes les valeurs. Dans ce cas, on utilise une Recherche dichotomique.

    Comme dans le choix des variables, l’utilisateur en connaît souvent plus sur le problème. Il peut donc proposer son propre choix de valeurs. Pour cela il doit implémenter une nouvelle stratégie en utilisant une « interface » bien précise.

L'algorithme de recherche va donc consister à choisir une stratégie puis à faire un parcours complet de l'arbre (les seules parties ignorées sont prouvées inconsistantes). L'algorithme est donc global car la recherche se fait en sachant à tout moment ce qui a été parcouru et ce qu’il reste à parcourir :

Explore( n ) {

// Création d'une heuristique.
b = getHeuristique( );

// Affectation du type de choix de variables.
v = b.selectBranchingObject( );

// Affectation du type de choix de valeurs.
i = b.getFirstBranch( x );

do {

// Sauvegarde du monde ( <=> l'état) courant.
pb.getEnvironment( ).worldPush( );

// Branchement sur une des valeurs.
b.goDownBranch( x, i );

// Appel récursive dans ce monde.
explore(n+1);

// Retour au monde sauvegardé.
pb.getEnvironment( ).worldPop( );

// Remontée dans l'arbre.
b.goUpBranch( x, i );

// Choix de la variable suivante.
i = getNextBranch( x, i );

}
while ( ! finishedBranch() );

}

Il est bien sûr possible de proposer des algorithmes non complets comme par exemple, la Limited Discrepancy Search qui consiste à ne pas s’éloigner de l’heuristique (au sens premier choix pris) plus de ‘k’ fois dans la branche en cours d’exploration.
.
Il ne s’agit cependant pas d’une utilisation classique de la PPC. La section suivante présente des techniques plus avancées de Recherche et Propagation.

 

Voici le plan de cette présentation sur la programmation par contraintes

Cette page a été co-réalisée avec Guillaume Rochart, docteur en mathématiques dans mon équipe de recherche au Bouygues e-lab.10/03/2009.