Problèmes de satisfaction de contraintes (CSP)
• Cours 1: Introduction
– Description du domaine d’applications
– Aperçus des modèles et algorithmes de résolutions
• Cours 2 : Modelisation
– Concept de bases : variables, domaines, contraintes
– Exemples
• Cours 3: Résolution
– Concept de base : recherche et propagation
– exemples
Modèle?
C’est quoi un modèle?
• Un modèle est une abstarction d’un problème
• Un modèle doit respecter le langage du solveur
(le solveur est une boite noire)
Meilleur est le modèle (et le solveur), meilleur est la solution
Coloriage de graphe
Coloriage des nœuds d’un graphe
• Quelle est le nombre minimal de couleur tel que deux nœuds
adjacents reçoivent des couleurs différentes?
Coloriage de graphe
Coloriage des nœuds d’un graphe
• Quelle est le nombre minimal de couleur tel que deux nœuds
adjacents reçoivent des couleurs différentes?
Coloriage de graphe
Comment colorier le graphe?
• Il y a 6 nœuds, donc un maximum de 6 couleurs :
Coloriage de graphe
Comment colorier le graphe?
Coloriage de graphe
Comment colorier le graphe?
Coloriage de graphe
Comment colorier le graphe?
Coloriage de graphe
Comment colorier le graphe?
Coloriage de graphe
Comment colorier le graphe?
Coloriage de graphe
Comment savoir si la solution est optimale?
La clique la plus large contient 3 nœuds :
On a besoins d’au moins 3 couleurs pour cette clique
• Une clique est un (sous)-graphe contenant une arête entre chaque deux noeuds
Coloriage de graphe : modèle
Etape 1 :
Donner à chaque nœud un nom : A, B, C, D, E, F.
Elle représente les couleurs à affecter aux nœuds
Par exemple ‘A = rouge’
• Elles représentent les variables
Coloriage de graphe : modèle
Etape 2 :
Initialement tous les nœuds peuvent être
{rouge, bleu, vert, jaune, blueciel, violet}
• Elles représentent les domaines des variables
Coloriage de graphe : modèle
Etape 3 :
Déclarer que deux nœuds adjacents ne peuvent prendre la même couleur
• Elles représentent les contraintes
Coloriage de graphe : modèle
Etape 4 :
Minimiser le nombre de couleurs
• Elle représente la fonction objectif
Coloriage de graphe : modèle
Modèle complet :
Variables : A, B, C, D, E, F
Domaines : {rouge, bleu, vert, jaune, blueciel, violet}
Contraintes :
Coloriage de graphe : modèle
Solution est :
Affecter pour chaque variable une couleur de manière à satisfaire toutes les
Contraintes
pas nécessairement optimale
Modélisation par des contraintes
En raisonnement par contraintes, un modèle est construit en utilisant
• des variables
• des domaines des variables
• des contraintes entre les variables
Un tel modèle est appelé Problème de Satisfaction de Contraintes (CSP)
Une solution à un CSP est :
– Affecter à chaque variable une valeur de son domaine de manière à satisfaire toutes
les contraintes
• Un solveur de contraintes permet de
– Trouver une solution au CSP,
– Ou de prouver qu’aucune solution n’existe.
Variables et domaines
Les variables peuvent avoir différents types de noms :
A, B, C, D, E, F
x1, x2, x3, x4, x5, x6
startT1, startT2, startT3, startT4
Le domaine des variables peut être fini ou infini :
{rouge, vert, bleu} tout type d’éléments
{0, 1, 2, 3, 4, 5} des entiers naturels
{ {a,b}, {a,c}, {b, c}, {a, b, c} } des ensembles
[0, 100] des nombres réels
Les contraintes
Une contrainte peut être toute relation sur un ensemble de variables,
par exemple :
Sur 1 variable A :
Sur une variable x :
Entre deux variables A et B :
Entre deux variables x et y :
Entre n variables : x1, x2, …, xn :
alldifferent(x1,x2,…,xn) toutes les variables doivent être deux à deux différentes
Les contraintes
D’autres types de contraintes :
Chaque librairie du langage a ses contraintes prédéfinies.
Votre modèle doit utiliser les contraintes du langage
Modélisation de problèmes combinatoires
Exemples :
• Puzzles crypto-arithmétique
• Carrés latin « Latin squares »
Puzzles Crypto-Arithmétique
Remplacer chaque lettre par par un chiffre distinct tel que :
est correcte
Puzzles Crypto-Arithmétique
Remplacer chaque lettre par par un chiffre distinct tel que :
est correcte
Carrés latin « Latin squares »
Etant donnée n couleurs, un carré latin (ou quasigroup) d’ordre n est un carré n x n colorié tel
que :
– Toutes cellule est coloriée
– Chaque couleur apparaît exactement une fois sur chaque ligne
– Chaque couleur apparaît exactement une fois sur chaque colonne
Carré latin d’ordre 4
Carrés latin « Latin squares »
Variables :
For row i in {1..n}
column j in {1..n}:
color[i,j]
Domaines : {1,2,…,n} « les couleurs »
color[4,3]
Contraintes :
For each row i in {1..n}:
alldifferent(color[i,1], color[i,2],.., color[i,n])
For each column j in {1..n}:
alldifferent(color[1,j], color[2,j],.., color[n,j])
Complétion d’un carré latin
Etant donnée une affectation partiel de couleurs (10 couleurs), est -ce que le carré latin
partiel peut être complété en un carré latin complet ?
Exemple:
32% de cellule colorées
Complétion d’un carré latin
Ajouter à la précédent modèle les contraintes suivantes :
(ici bleu = 1, jaune = 2, rouge = 3, vert = 4)
Problème d’investissements
Budget : 14000$
Problème d’investissements
Budget : 14000$
Problème d’investissements
Un autre modèle
n-Reines
Placer n reines sur un échiquier n x n tel que
deux reines ne soient pas en prises
Comment modéliser ce problème?
Sudoku
Un sudoku partiellement complété, trouvez la solution?
Comment modéliser ce problème ?