Utiliser la PPC pour déterminer s’il y a des solutions à notre problème peut être utile mais pas suffisant. De nombreux utilisateurs souhaitent savoir pourquoi on ne trouve pas de solutions, en particulier dans les applications d'aide à la décision où les intéractions entre l'utilisateur et le moteur de calcul sont nombreuses. La manière la plus « simple » est de répondre à la requête suivante :

Fournir un ensemble (si possible aussi petit que possible) de contraintes n’ayant pas de solutions communes. Ce lot de contraintes va expliquer pourquoi notre problème est inconsistant et ne peut être résolu. Si on considère l'exemple suivant :

AllDifferent( a, b, c, d )
a = e
a = b = c = d = e = [1,3]

Le problème est inconsistant. Or la contrainte a = e n’a rien à voir avec le problème : on souhaite donc avoir comme explication AllDifferent( a, b, c, d ).

La première méthode pour calculer les explications consiste à faire une recherche dichotomique sur les contraintes. Par exemple, si on a les contraintes c1, c2, c3, c4, et c5. On va essayer de résoudre le problème avec c1. Si il n'y a pas de problème, ce n’est pas une explication. On ajoute c2, pas de contradiction. On ajoute c3, on a une contradiction, donc c1 et c2 et c3 forment une explication à la contradiction. Tentons, le problème avec c2 et c3, on a une contradiction donc une autre explication plus précise se dessine. La méthode est connue sous le nom de QuickXPlain. Elle est intéressante car elle ne nécessite pas de nouveaux outils mais peut nécessiter de nombreuses résolutions.

Une autre solution consiste à toujours garder des explications justifiant tout domaine. Ainsi, dès qu’une variable a une valeur retirée, la contrainte responsable doit fournir une explication justifiant ce retrait. Par exemple, si l’on a x = y et que la valeur 5 est retirée de x, alors l’algorithme de filtrage va retirer la valeur 5 de y. L’explication fournie sera alors l’explication du retrait de 5 du domaine de x à laquelle on ajoutera la contrainte x = y. Cette technique est utilisée par exemple dans le module Palm de Choco.

La principale limitation des explications vient de la nécessité de fournir des versions expliquées de chaque contrainte. Résoudre un problème + fournir des explications est un problème beaucoup plus complexe que de simplement le résoudre. Il est donc normal que cela prenne du temps en plus même si l’on utilise des algorithmes dédiés. Cependant, on remarque souvent sur de problèmes réels un facteur 2 ce qui est plus qu’acceptable étant donné le gain que cela peut apporté à l'utilisateur final.

 

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

• Les notions de base :
  • Les C.S.P.
  • La Recherche / Propagation
    
    
• Quelques notions avancées :
• Les Contraintes Globales
• Le Continu
• Les Explications
  
  
• Quelques exemples pour utiliser la P.P.C. :
  • Les N-Reines
  • Send More Money
  • Le Sudoku
  • Le Kakuro
  • Picross

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.