Introduction à la PPC

Les CSPs
Les CSPs distribués

La Programmation Par Contraintes

Les CSPs et CSP distribués : Modéle et résolution

Imade Benelallam

[email protected]
Département Informatique
Institut National de Statistique et d’Economie Appliquée, Rabat

2 octobre 2014

Imade Benelallam La Programmation Par Contraintes

 Introduction à la PPC
Les CSPs
Les CSPs distribués

Préalable

Buts du cours
Comprendre le paradigme de la Programmation Par Contraintes (PPC).
Maı̂triser le formalisme des problèmes de Satisfaction de contraintes (CSP).
Apprendre à modèliser les problèmes en utilisant les CSPs.
Maı̂triser les principales techniques de résolution des problèmes combinatoires
(les notions de filtrage et de propagation).

Imade Benelallam La Programmation Par Contraintes

 Introduction à la PPC
Les CSPs
Les CSPs distribués

Préalable

Pré-requis
IA I.
Notions sur la théorie des graphes.
Notions sur la théorie de complexité.
Langage Java (outil d’implémentation).

Imade Benelallam La Programmation Par Contraintes

 Introduction à la PPC
Les CSPs
Les CSPs distribués

Plan

Modélisation
1 Introduction à la PPC Résolution
Définitions Graphe de contraintes
Repéres historiques Algorithmes de résolution
Exemples de problèmes TP : Solveurs Choco
Applications industrielles
Solveurs existants
2 Les CSPs
Définition

Imade Benelallam La Programmation Par Contraintes

 Introduction à la PPC
Les CSPs
Les CSPs distribués

Plan

Modélisation
1 Introduction à la PPC Résolution
Définitions Graphe de contraintes
Repéres historiques Algorithmes de résolution
Exemples de problèmes TP : Solveurs Choco
Applications industrielles 3 Les CSPs distribués
Solveurs existants Définition
2 Les CSPs Approche Synchrone : SBT
Définition Approche Asynchrone : ABT

Imade Benelallam La Programmation Par Contraintes

 Introduction à la PPC
Les CSPs
Les CSPs distribués

Plan

Modélisation
1 Introduction à la PPC Résolution
Définitions Graphe de contraintes
Repéres historiques Algorithmes de résolution
Exemples de problèmes TP : Solveurs Choco
Applications industrielles 3 Les CSPs distribués
Solveurs existants Définition
2 Les CSPs Approche Synchrone : SBT
Définition Approche Asynchrone : ABT

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Style de programmation

Différents pradigmes de programmation

Programmation structurée : Pascal, C, ...

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Style de programmation

Différents pradigmes de programmation

Programmation structurée : Pascal, C, ...
Programmation fonctionnelle : Lisp, Caml, ...

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Style de programmation

Différents pradigmes de programmation

Programmation structurée : Pascal, C, ...
Programmation fonctionnelle : Lisp, Caml, ...
Programmation orientée objets : C++, JAVA, ...

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Style de programmation

Différents pradigmes de programmation

Programmation structurée : Pascal, C, ...
Programmation fonctionnelle : Lisp, Caml, ...
Programmation orientée objets : C++, JAVA, ...
Programmation logique : Prolog, Mercury, ...

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Style de programmation

Différents pradigmes de programmation

Programmation structurée : Pascal, C, ...
Programmation fonctionnelle : Lisp, Caml, ...
Programmation orientée objets : C++, JAVA, ...
Programmation logique : Prolog, Mercury, ...

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Programmation par contraintes

Constraint Programming
”Constraint programming represents one of the closest approaches
computer science has made to the Holy Grail of programming : the
user states the problem, the computer solves it.”

Eugene C. Freuder, CONSTRAINTS, Avril 1997

Programmation par contraintes = architecture a 2 niveaux :

1 Langage des contraintes : un ensemble dénombrable de
symboles de prédicats (store de contraintes)

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Programmation par contraintes

Constraint Programming
”Constraint programming represents one of the closest approaches
computer science has made to the Holy Grail of programming : the
user states the problem, the computer solves it.”

Eugene C. Freuder, CONSTRAINTS, Avril 1997

Programmation par contraintes = architecture a 2 niveaux :

1 Langage des contraintes : un ensemble dénombrable de
symboles de prédicats (store de contraintes)
2 Solveur de contraintes : Réduction des domaines des objets
par considération des contraintes de store ;

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Programmation par contraintes

Constraint Programming
”Constraint programming represents one of the closest approaches
computer science has made to the Holy Grail of programming : the
user states the problem, the computer solves it.”

Eugene C. Freuder, CONSTRAINTS, Avril 1997

Programmation par contraintes = architecture a 2 niveaux :

1 Langage des contraintes : un ensemble dénombrable de
symboles de prédicats (store de contraintes)
2 Solveur de contraintes : Réduction des domaines des objets
par considération des contraintes de store ;

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Programmation par contraintes

On se trouve où ?
Un problème, une solution : la solution est-elle une solution
du problème ? ⇒ simulation, vérification
Un problème : trouver la meilleure solution du problème ⇒
programmation linéaire
Un problème : trouver une, toutes ou la solution
optimale du problème ⇒ programmation par contrainte
(CSP)

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Programmation par contraintes

Problème NP-complets
La PPC s’intéresse aux problèmes NP-difficile vérifiant les
propriétés suivantes :
toute solution est vérifier efficacement en un temps
polynomial.
Aucun problème de classe NP n’est résolut par un algorithme
polynomial ! ! !

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Programmation par contraintes

Objectif
Trouver une solution réalisable
Qui respecte des contraintes faciles à vérifier : Formules
mathématiques simples, tableaux de valeurs possibles
Avec des ensembles de valeurs possibles pour les variables de
décision

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Définition d’une contrainte

Une contrainte est une relation entre des variables

Une contrainte restreint les valeurs que l’on peut affecter
simultanément à des variables

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Définition d’une contrainte

Une contrainte est une relation entre des variables

Une contrainte restreint les valeurs que l’on peut affecter
simultanément à des variables
Une contrainte peut spécifier de l’information partielle (l’âge
du prof est au moin supérieur à 20)

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Définition d’une contrainte

Une contrainte est une relation entre des variables

Une contrainte restreint les valeurs que l’on peut affecter
simultanément à des variables
Une contrainte peut spécifier de l’information partielle (l’âge
du prof est au moin supérieur à 20)
Une contrainte est déclarative (indépendante du processus
opérationnel)

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Définition d’une contrainte

Une contrainte est une relation entre des variables

Une contrainte restreint les valeurs que l’on peut affecter
simultanément à des variables
Une contrainte peut spécifier de l’information partielle (l’âge
du prof est au moin supérieur à 20)
Une contrainte est déclarative (indépendante du processus
opérationnel)
Une contrainte est non-directionnelle (relationnelle) :
x + y = z : si x et y sont connus, on détermine z ; si x et z
son connus, on détermine y ,...

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Définition d’une contrainte

Une contrainte est une relation entre des variables

Une contrainte restreint les valeurs que l’on peut affecter
simultanément à des variables
Une contrainte peut spécifier de l’information partielle (l’âge
du prof est au moin supérieur à 20)
Une contrainte est déclarative (indépendante du processus
opérationnel)
Une contrainte est non-directionnelle (relationnelle) :
x + y = z : si x et y sont connus, on détermine z ; si x et z
son connus, on détermine y ,...
L’ordre de pose des contraintes est indifférent pour la
sémantique
Imade Benelallam La Programmation Par Contraintes
 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Définition d’une contrainte

Une contrainte est une relation entre des variables

Une contrainte restreint les valeurs que l’on peut affecter
simultanément à des variables
Une contrainte peut spécifier de l’information partielle (l’âge
du prof est au moin supérieur à 20)
Une contrainte est déclarative (indépendante du processus
opérationnel)
Une contrainte est non-directionnelle (relationnelle) :
x + y = z : si x et y sont connus, on détermine z ; si x et z
son connus, on détermine y ,...
L’ordre de pose des contraintes est indifférent pour la
sémantique
Imade Benelallam La Programmation Par Contraintes
 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Définition d’une contrainte

Déclaration
en extension : on énumère les valeurs admises
(x = 1, y = 2)ou(x = 2, y = 4)ou(x = 3, y = 0)
en intension : on utilise les signes mathématiques connus x < y
arité d’une contrainte
unaire : porte sur 1 variable
binaire : porte sur 2 variables
...
n-aire : porte sur n variables

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Contraintes numérique

Contrainte atomique :
x2 = 2 (1)
⇒ le domaine des variables doit être connu :
x rationnel : pas de solution
√ √
x réel : deux solutions possibles {− 2, 2}
Plus généralement :

x2 − y = 0 ∧ x2 + y2 = 1 (2)

Conjonctions, disjonctions, négations de contraintes atomiques

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Contraintes booléenes

Figure: Additionneur

Modélisation :
(I 1 ⇔ X ∧ Y ) ∧ (I 2X ⊕ Y ) ∧ (I 3 ⇔ I 2 ∧ CI ) ∧ (O ⇔
I 2 ⊕ CI ) ∧ (CO ⇔ I 1 ∨ I 3)
Imade Benelallam La Programmation Par Contraintes
 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Contraintes logique

Si x = 4 alors y = 5
x = y ou x = 2y

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Contraintes globales

atmost
atmost(2, [X1 , X2 , X3 , X4 ], 1)
Au plus 2 variables parmi {X1 , X2 , X3 , X4 } sont égales à 1.

Alldiff

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Contraintes globales

atmost
atmost(2, [X1 , X2 , X3 , X4 ], 1)
Au plus 2 variables parmi {X1 , X2 , X3 , X4 } sont égales à 1.

Alldiff
alldiff ([X1 , X2 , X3 , X4 ])
Les variables {X1 , X2 , X3 , X4 } ont des valeurs différentes deux à
deux.

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Contraintes globales

atmost
atmost(2, [X1 , X2 , X3 , X4 ], 1)
Au plus 2 variables parmi {X1 , X2 , X3 , X4 } sont égales à 1.

Alldiff
alldiff ([X1 , X2 , X3 , X4 ])
Les variables {X1 , X2 , X3 , X4 } ont des valeurs différentes deux à
deux.

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Repéres historiques (1)

1972 - 1974 : PROLOG (Luminy). A. Colmerauer P. Roussel

1974 : définition d’un CSP. U. Montanari
1976 : ALICE premier langage à base de contraintes J. L.
Lauriére
1977 Warren Abstract Machine (WAN)
1977 définition de la consistance de A. K. Mackworth

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Repéres historiques (2)

1984 PROLOG III, intogration des contraintes numériques

1987 création d’ILOG par P. Haren
1993 Fondements de la satisfaction de contraintes. E. Tsang
1993 PLC concurrente. W. A. Sarawat
1995 PROLOG standard : ISO 13211-1
1998 Régles de traitement des contraintes (CHR). T.
Frühwirth

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Exemple introductif : Sudoku (1)

3 4 5 7
6 2 8 4
7 1 9
2 4 6 3 8
2 3
1 3 6 9 5
8 4 7
1 9 6
9 5 3 8 2

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Exemple introductif : Sudoku (2)

3 4 5 7
6 2 8 4
7 1 9
2 4 6 3 8
2 3
1 3 6 9 5
8 4 7
1 9 6
? 9 5 3 8 2
1 2 3 4 5 6 7 8 9?

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Exemple introductif : Sudoku (3)

3 4 5 7
6 2 8 4
7 1 9
2 4 6 3 8
2 3
1 3 6 9 5
8 4 7
1 9 6
? 9 5 3 8 2
1 2 3 4 5 6 7 8 9?
lignes : 2 3 5 8 9 colonnes : 1 2 6 7

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Exemple introductif : Sudoku (4)

suite aux éliminations :

3 4 5 7
6 2 8 4
7 1 9
2 4 6 3 8
2 3
1 3 6 9 5
8 4 7
1 9 6
4 9 5 3 8 2

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Exemple introductif : Sudoku (5)

? 3 4 5 7
6 2 8 4
7 1 9
2 4 6 3 8
2 3
1 3 6 9 5
8 4 7
1 9 6
4 9 5 3 8 2
1 2 3 4 5 6 7 8 9?

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Exemple introductif : Sudoku (6)

? 3 4 5 7
6 2 8 4
7 1 9
2 4 6 3 8
2 3
1 3 6 9 5
8 4 7
1 9 6
9 5 3 8 2
1 2 3 4 5 6 7 8 9?
lignes : 3 4 5 7 colonnes : 1 2 6 7
réduction du domainee 8 ou 9 ?

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Exemple introductif : Sudoku (7)

8 ou 9 3 ? 4 5 7
6 2 8 4
7 1 9
2 4 6 3 8
2 3
1 3 6 9 5
8 4 7
1 9 6
4 9 5 3 8 2
1 2 3 4 5 6 7 8 9?
lignes : 3 4 5 7 colonnes : 3 6 8 9
réduction du domaine : 1 ou 2 ?
raisonnement local : 2 est déjà dans le carré donc c’est 1
Imade Benelallam La Programmation Par Contraintes
 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Sudoku et programmation par contraintes

raisonnement par élimination, réduction du domaine

raisonnement local
transmission des déductions aux autres régions
3 principes au coeur de la programmation par contraintes

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Exemple : Le Problème de n-Reines

Parmi les problèmes de CSP les plus connus figurent le problème
des reines. Le problème des reines consiste à placer n reines sur un
échiquier comportant n lignes et n colonnes, de manière à ce
qu’aucune reine ne soit en prise. On rappelle que 2 reines sont en
prise si elles se trouvent sur une même diagonale, une même ligne
ou une même colonne de l’êchiquier ;

(a) solution 1 (b) solution 2

Imade Benelallam La Programmation Par Contraintes
 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Exemple :Le Problème du Voyageur de Commerce (PVC)

Le PVC est un problème NP-difficile.

Il consiste à visiter n villes données de telle sorte que le cout
(on dit aussi poid ou valuation) soit optimal (ici la distance
parcourue doit être minimale).
Le cycle parcouru doit être hamiltonien.
Un cycle est hamiltonien si et seuleument si chaque ville existe
une et une seule fois dans le cycle :
On sort une et une seule fois de chaque ville du domaine
On y accéde une et une seule fois.

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Applications
NASA et the European Space Agency
Télescope spatial (Hubble Space Telescope) : CBI
(Constraint-Based Interval) planners Algorithms

(c) (d)

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Applications
British Airways & IBM
la planification des vols et l’allocation des positions d’avions.
la conception de puces et la génération automatique de tests.

(a) (b)

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Conception de matériel informatique

vérification de circuits
connexion des couches de circuits
moins efficace que le code dédié mais plus flexible
utilisateur : Dassault, Siemens

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Placement d’objets

placement de containers
remplissage de containers
utilisateur : Michelin

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Problème de découpage

minimisation de pertes lors de la découpe de matériaux

(papier, verre, bois, métaux, ...)
utilisateur : Dassault pour les pièces d’avion
performances dépendent du contexte
papier : facile, programmation linèaire
métaux : plus difficile, programmation par contraintes

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Allocation d’espace

portes pour les avions

quais pour les trains et les bateaux
utilisateur : Aéroport CDG

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Allocation de fréquance

trouver des fréquences radio pour les :

tèléphones portables
communication radio
armée ...

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Ordonnancement de la production

planifier les tâches sur des machines dans une usine

plus important succès de la PPC
meilleures performances que la RO
plusieurs installations commerciales
librairies dédiées à l’ordonnacement (ILOG scheduler)

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Emplois du temps

construction des emplois du temps universitaire :

Une application concréte dans notre université.
construction d’horaires de personnel : santé, commerce, usine,
...
planification des équipages sur les avions, les trains
tournée de véhicules

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Solveurs présents sur le marché (1)

systèmes basés sur la programmation logique

SICStus Prolog (www.sics.se/sictus/)
ECLiPSE Prolog (www.icparc.ic.ac.uk/eclipse)
GNU Prolog (gprolog.inria.fr)
CHIP (www.cosytec.fr)

Imade Benelallam La Programmation Par Contraintes

 Définitions
Introduction à la PPC Repéres historiques
Les CSPs Exemples de problèmes
Les CSPs distribués Applications industrielles
Solveurs existants

Solveurs présents sur le marché (2)

systèmes basés sur des librairies

ILOG soveur (C++) (www.ilog.com/products/solver/)
JSolver (Java) (www.ilog.com/products/jsolver/)
Choco (Java) (www.choco-constraints.net)
Facile (Ocaml) (www.recherche.enac.frslashopti/facile/)
CHIP Library (C++)(www.cosytec.fr)
JLC (Java) (liawww.epf1.ch/JCL/icl-index.html)

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Bibliographie

Livres :
K. Marriott and P. Stuckey. Programming with constraints.
MIT Press 1998
F. Fages. Programming Logique par contraintes. Ellipes, 1996
K. R. Apt. Principles in Constraint Programming. Cambridge
Univ Press, 2003
Supports de cours :
Support de cours : Christine SOLNON université Lyon I :
http ://bat710.univ-lyon1.fr/ csolnon/Site-PPC/
Roman Bartak Charles university : http ://kti.mff.cuni.cz/
bartak/constraints/

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Problèmes de Satisfaction de Contraintes (CSP)

Définition
un CSP est un problème modélisé sous forme de contraintes posées
sur des variables prenant valeur dans un domaine

un CSP est un quadruplet (X,D, C, R) où :

X = {X1 , ..., Xn } : un ensemble de variables
D = {D1 , ..., Dn } : un ensemble de domaines,
Xi ∈ Di , 1 ≤ i ≤ n
C = {C1 , ..., Cm } : un ensemble de contraintes,
R = {R1 , .., Rm } : un ensemble de relations,
à chaque contrainte Cj est associée une relation Rj ,
1≤j ≤m
Imade Benelallam La Programmation Par Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Problèmes de Satisfaction de Contraintes (CSP)

Exemple
X = {X1 , X2 , X3 , X4 }
D = {D1 , D2 , D3 , D4 }, avec D1 = D2 = D3 = D4 = {0, 1}
C = {X1 6= X2 , X3 6= X4 , X1 + X3 < X2 }
R = {R1 , R2 }

R1 R1
X1 X2 X3 X4
0 1 0 1
1 0 1 0
R2
X1 X2 X3
0 1 0
Imade Benelallam La Programmation Par Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Modélisation de problème en termes de CSP (1)

Modélisation d’un problème

identifier les variables : les inconnues

identifier les domaines de valeur de ces variables
identifier les contraintes
souvent plusieurs modélisations possibles, critères de choix :
simplicité d’expression
efficacité : taille de l’espace de recherche de solutions

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Modélisation de problème en termes de CSP (2)

Exemple : le problème des 4 reines

Placer 4 reines sur échiquier 4 × 4 de telle sorte qu’aucune ne soit
en prise (pas sur la même ligne, pas sur la même colonne, pas sur
la même diagonale)

X= ?
D= ?
C= ?

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Modélisation de problème en termes de CSP (3)

Exemple : le problème des 4 reines
Placer 4 reines sur échiquier 4 × 4 de telle sorte qu’aucune ne soit
en prise (pas sur la même ligne, pas sur la même colonne, pas sur
la même diagonale)

X = {X1 , X2 , X3 , X4 }
D = {D1 , D2 , D3 , D4 } avec D1 = D2 = D3 = D4 = {1, 2, 3, 4}
C = CLI , CDA , CDD avec
CLI = {Xi 6= Xj, i 6= j, i ∈ {1, 2, 3, 4}, j ∈ {1, 2, 3, 4}}
CDA = {Xi + i 6= Xj + j, i 6= j, i ∈ {1, 2, 3, 4}, j ∈ {1, 2, 3, 4}}
CDD = {Xi − i 6= Xj − j, i 6= j, i ∈ {1, 2, 3, 4}, j ∈ {1, 2, 3, 4}}

Modélisation efficace
Imade Benelallam La Programmation Par Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Résolution d’un CSP (1)

Résolution :
Affectation de valeurs aux variables de telle sorte que toutes les
contraintes soient satisfaites

affectation : instanciation des variables sur les domaines

affectation totale : affectation de toutes les variables
affectation partielle : affectation de certaines variables
affectation consistante : affectation qui ne viole aucune
contrainte
affectation inconsistante : affectation qui viole au moins une
contrainte
solution : affectation totale et consistante
Imade Benelallam La Programmation Par Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Résolution d’un CSP (2)

Exemple
X = {X1 , X2 , X3 , X4 }
D = {D1 , D2 , D3 , D4 } avec D1 = D2 = D3 = D4 = {0, 1}
C = {X1 6= X2 , X3 6= X4 , X1 + X3 < X2 }

A = {(X2 , 0), (X3 , 1)} affectation

A = {(X1 , 0), (X2 , 0), (X3 , 0), (X4 , 0)} affectation totale
A = {(X1 , 0), (X2 , 0)} affectation partielle
A = {(X1 , 0), (X2 , 0)} affectation inconsistante
A = {(X3 , 0), (X4 , 1)} affectation consistante
A = {(X1 , 0), (X2 , 1), (X3 , 0), (X4 , 1)} solution
Imade Benelallam La Programmation Par Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Résolution d’un CSP (2)

Exemple
X = {X1 , X2 , X3 , X4 }
D = {D1 , D2 , D3 , D4 } avec D1 = D2 = D3 = D4 = {0, 1}
C = {X1 6= X2 , X3 6= X4 , X1 + X3 < X2 }

A = {(X2 , 0), (X3 , 1)} affectation

A = {(X1 , 0), (X2 , 0), (X3 , 0), (X4 , 0)} affectation totale
A = {(X1 , 0), (X2 , 0)} affectation partielle
A = {(X1 , 0), (X2 , 0)} affectation inconsistante
A = {(X3 , 0), (X4 , 1)} affectation consistante
A = {(X1 , 0), (X2 , 1), (X3 , 0), (X4 , 1)} solution
Imade Benelallam La Programmation Par Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Résolution d’un CSP (3)

Résolution
Affectation de valeurs aux variables de telle sorte que toutes les
contraintes soient satisfaites

complexité : en général problème NP-difficile

solution : affectation totale et consistante
On peut chercher :
une solution, n’importe laquelle
toutes les solutions
une solution optimale ou au moins une bonne solution selon
une fonction de coût ou d’objectif (Problème d’Optimisation
de Contraintes (COP))
Imade Benelallam La Programmation Par Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Intérêt des CSP

Intérêt des CSP par rapport à la programmation mathématique

la représentation des CSP est plus proche des problèmes
originaux, la formulation est plus simple
les algorithmes de résolution des CSP sont relativement
simples et sont plus rapides que ceux de la programmation en
nombres entiers

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Binarisation des contraintes (1)

Les contraintes peuvent être n-aires : 2 cas particuliers

les contraintes unaires : peuvent être traitées par un
pré-traitement sur les domaines
les contraintes binaires : si toutes les contraintes sont
binaires : représentation par un graphe dont les sommets sont
les variables et les arcs sont les contraintes.
toute contrainte n-aire : peut s’exprimer en termes de
contraintes binaires

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Binarisation des contraintes (2)

toute contrainte n-aire peut s’exprimer en termes de

contraintes binaires
tout CSP peut se représenter comme un CSP binaire
un CSP binaire peut être représenté comme un graphe de
contraintes

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Binarisation d’un CSP (3)

Méthode 1 : conservation de variables initiales

création d’une variable encapsulée U
domaine de U : produit cartésien des variables encapsulées
application des contraintes sur les variables encapsulées pour
réduire le domaine CSP binaire
ajout d’une contrainte binaire entre la variable originale et la
variable encapsulée : Xi = posi (U)
ième position de Xi dans U : posi (U)

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Binarisation d’un CSP (4)

Méthode 1 : exemple
X = {X1 , X2 , X3 }
D = {D1 , D2 , D3 } avec D1 = {1, 2}, D2 = {3, 4}, D3 = {5, 6}
C = {X1 + X2 = X3 , X1 < X2 }

CSP binaire : X 0 = {X1 , X2 , X3 , U}, D 0 = {D1 , D2 , D3 , DU0 }

création de la variable
U = {(X1 , X2 , X3 )}, tq{X1 + X2 = X3 }, DU = D1 × D2 × D3
réduction de domaine : DU0
nouvel ensemble de containtes : C 0

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Binarisation d’un CSP (4)

Méthode 1 : exemple
X = {X1 , X2 , X3 }
D = {D1 , D2 , D3 } avec D1 = {1, 2}, D2 = {3, 4}, D3 = {5, 6}
C = {X1 + X2 = X3 , X1 < X2 }

CSP binaire : X 0 = {X1 , X2 , X3 , U}, D 0 = {D1 , D2 , D3 , DU0 }

création de la variable
U = {(X1 , X2 , X3 )}, tq{X1 + X2 = X3 }, DU = D1 × D2 × D3
réduction de domaine : DU0
nouvel ensemble de containtes : C 0

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Binarisation d’un CSP (5)

Méthode 2 : sans conservation de variables initiales

création de variables encapsulées
domaine : produit cartésien des variables qu’elles encapsulent
application des contraintes sur les variables encapsulées pour
réduire le domaine
ajout d’une binaire entre la variable originale et la variable
encapsulée : Xi = posi (U)
ième position de la variable encapsulée U est la jème position
de la variable encapsulée V : posi (U) = posj (V )

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Binarisation d’un CSP (6)

Méthode 2 : exemple
X = {X1 , X2 , X3 }
D = {D1 , D2 , D3 } avec D1 = {1, 2}, D2 = {3, 4}, D3 = {5, 6}
C = {X1 + X2 = X3 , X1 < X2 }

CSP binaire : X 0 = {U, V }, D 0 = {DU0 , DV0 }, C 0

création de 2 variable U = {(X1 , X2 , X3 ), tq{X1 + X2 = X3 }, et
V = {(X1 , X2 ), tq{X1 < X2 }DU = D1 × D2 × D3 et
DV = D1 × D2 }
réduction de domaine : DU0 et DV0
nouvel ensemble de containtes : C 0

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Graphe de contraintes

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Noeuds : Variables

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Domaines de variables

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Arc : Contraintes

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Densité

Densité d’un réseau de contraintes :

Pour un réseau de contraintes, on appelle densité (connectivité) de
contraintes, p1, le nombre total de contraintes existantes dans le
réseau par rapport au nombre maximal de contraintes qu’il peut
avoir. Pour un réseau de n variables avec c contraintes d’arité k, on
aura alors la densité p1 :

c
p1 = (3)
Cnk

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Dureté

Dureté d’une contrainte :

On appelle dureté p2 d’une contrainte la proportion de tuples
interdits par cette contrainte. Pour une contrainte d’arité k portant
sur des variables dont les domaines sont de taille d, décrite par c
tuples interdits, on aura la dureté p2 :

c
p2 = (4)
dk

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Résolution d’un CSP

hypothèse : domaines finis

algorithmes génériques de résolution de CSP

algorithmes complets
algorithmes incomplets
Autres algorithmes pour :
CSP numériques linéaires sur les réels
CSP numériques linéaires sur les entiers
CSP numériques non linéaires

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Critrès de comparaison de méthodes de résolution de CSPs

Les deux critères les plus utilisés pour comparer les algorithmes de
résolution en CSP sont le nombre de noeud visités et le nombre de
contraintes testées. Ces critères sont mesurés en fonction de la
densité et la dureté des contraintes.

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Nombre de noeuds visités

A chaque fois que le nombre de noeuds visités diminue, c’est a dire

qu’à chaque fois qu’on fait moins d’instantiations, l’arbre de
recherche devient moin large et alors optimale. Une méthode de
résolution de CSP est alors meilleure à chaque fois que le nombre
de noeuds visités est petit.

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Algorithmes de résolution d’un CSP

algorithmes génériques de résolution de CSP
recherche systématique
genere et teste (GET)
retour arrière (SRA) ou (backtracking (BT))
backjumping (BJ)
conflict directed backjumping (CBJ)
dynamique backtracking
techniques de filtrage
consistance de noeud (NC), d’arc (AC), de chemin (PC)...
techniques de propagation de contraintes
forward checking (FC)
look ahead (LH)
techniques basées sur l’ordre des variables et des valeurs
heuristiques
Imade Benelallam La Programmation Par Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

L’algorithme GET (1)

principe

Recherche systématique d’une solution

génération d’une affectation totale
test de la satisfaction de toutes les contraintes

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

L’algorithme GET (2)

fonction GET(A,(X,D,C)) : booléen
début
si (toutes les variables de X sont affectées) alors
si (A est consistante) alors
retourner VRAI
sinon
retourner FAUX
finsi
sinon
choisir une variable Xi de X qui n’est pas encore affectée
pour (toute valeur Vi appartenant à Di ) faire
si (GET(A ∪ {(Xi ,Vi )}, (X,D,C)) = VRAI) alors
retourner VRAI
finsi
finpour
retourner FAUX
finsi
fin Imade Benelallam La Programmation Par Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

L’algorithme GET (3)

Exemple
X = {X1 , X2 , X3 , X4 }
D = {D1 , D2 , D3 , D4 } avec D1 = D2 = D3 = D4 = {0, 1}
C = {X1 6= X2 , X3 6= X4 , X1 + X3 < X2 }
R = {R1 , R2 , R3 }

Rechercher la solution de ce CSP par l’algorithme GET ?

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

L’algorithme GET (4)

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

L’algorithme GET (5)

Inconvenients sur l’espace de recherche

ensemble des affectations complètes
inconsistance d’écouverte au dernier moment
croissance exponentielle de la taille de l’espace de recherche

Améliorations
ne développer que des affectations partielles consistantes
réduire la taille des domaines

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

L’algorithme BT (1)

principe

Construction d’une solution

génération d’un affectation partielle consistante
extension de l’affectation partielle avec l’affection d’une
nouvelle variable
si cette extension est inconsistante on retourne en arrière on
modifie l’affectation de la nouvelle variable

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

L’algorithme BT (2)
fonction SRA(A,(X,D,C)) : booléen
début
si (A n’est pas consistante) alors
retourner FAUX
finsi
si (toutes les variables de X sont affectées) alors
retourner VRAI
sinon
choisir une variable Xi de X qui n’est pas encore affectée
pour (toute valeur Vi appartenant à Di ) faire
si (SRA(A ∪ {(Xi ,Vi )}, (X,D,C)) = VRAI) alors
retourner VRAI
finsi
finpour
retourner FAUX
finsi
fin
Imade Benelallam La Programmation Par Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

L’algorithme BT (3)

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

L’algorithme BT (4)

exemple du problème des 4 reines

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

L’algorithme BT (5)

Avantages
réduction de l’espace de recherche
améliore GET en espace et en temps d’exécution

Inconvenients
pas d’identification des cause de conflit
redondance
détection tardive des conflits
alternatives : backjumping, backmarking, Dynamic reordring

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Techniques de filtrage
La technique du backtrack induit une exploration exhaustive de
l’espace de recherche, de taille d n ; l’obtention d’une solution
nécessite donc un temps de calcul de l’ordre de c ∗ d n , où c est le
nombre des contraintes, n celui des variables et d la taille des
domaines. Plusieurs techniques ont donc été étudiées afin
d’accroı̂tre l’efficacité de résolution des CSP. Une des plus utilisées
est le filtrage par consistance.
principe
filtrage des domaines
dans la construction d’une affectation partielle consistante :
filtrage à priori
filtrer le domaine des variables en enlevant les valeurs
localement inconsistantes
filtrage à différents niveaux : noeud, arc, chemin, ...
Algorithmes :ImadeAC1, AC2, AC3,
Benelallam AC4, AC5,ParAC6,
La Programmation AC7, AC8,
Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Techniques de filtrage

Consistance de noeud
Un CSP (X , D, C , R) est consistant de noeud si pour toute
variable Xi de X , et pour toute valeur v de Di , l’affectation
partielle {(Xi , v )} satisfait toutes les contraintes unaires de C .

Principe
filtrage des domaines
pour chaque variable Xi , on enlève de Di toute valeur v telle
que l’affectation partielle {(Xi , v )} viole les contraintes
unaires.

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Techniques de filtrage

Consistance d’arc
Un CSP (X , D, C , R) est consistant d’arc si tout couple de
variables (Xi , Xj ) de X , et pour toute valeur vi de Di , il existe une
valeur vj appartenant Dj telle que l’affectation partielle
{(Xi , vi ), (Xj , vj )} satisfasse toutes les contraintes binaires de C.

Principe
filtrage des domaines
pour chaque variable Xi , on enlève de Di toute valeur vi telle
qu’il existe une variable Xj pour laquelle, pour toute valeur vj
de Dj , l’affectation partielle {(Xi , vi ), (Xj , vj )} viole les
contraintes binaires.

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Techniques de filtrage : consistance d’arc

Plusieurs algorithmes
AC ou REVISE : réduit la taille des domaines, supprime les
valeurs qui violent les contraintes binaires
AC1 : réapplique REVISE chaque fois qu’un domaine est
changé
AC3 : ne réapplique REVISE que le nombre de fois nécessaires

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Algorithme Consistance D’Arc : AC

fonction REVISE((Xi , Xj ), (X , D, C)) : booléen

début
DELETE ← FAUX
pour (tous les Vi de Di ) faire
si (il n’y a pas de Vj dans Dj qui satisfasse les contraintes binaires
entre Xi et Xj ) alors
supprimer Vi de Di
DELETE ← VRAI
finsi
finpour
retourner DELETE
fin

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Algorithme Consistance D’Arc : AC1

fonction AC1((X,D,C))
début
Q ← {(Xi , Xj ) / il existe une contrainte entre Xi et Xj }
répéter
R ← FAUX
pour (tous les (Xi , Xj ) de Q) faire
R ← (R ou REVISE((Xi , Xj ), (X, D, C)))
finpour
jusqu’à non R
retourner (X,D,C)
fin

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Algorithme Consistance D’Arc : AC3

fonction AC3((X,D,C))
début
Q ← {(Xi , Xj ) / il existe une contrainte entre Xi et Xj }
tantque (Q 6= ∅) faire
Q ← Q \ (Xi , Xj )
si (REVISE((Xi , Xj ),(X, D, C))) alors
Q ← Q ∪{(Xk , Xi ) / il existe une contrainte entre Xk et Xi et Xk 6= Xi
et Xk 6= Xj }
finsi
fintantque
retourner (X,D,C)
fin

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Techniques de filtrage : consistance locale

plusieurs notions

1-consistance : consistance de noeud

2-consistance : consistance d’arc
3-consistance : consistance de chemin
un ensemble {Xi , Xj } est consistant de chemin par rapport à
la variable Xk de X , si pour toute affectation partielle
{(Xi , vi ), (Xj , vj )}, il existe une valeur vk appartenant Dk telle
que {(Xi , vi ), (Xk , vk )} est consistant et {(Xk , vk ), (Xj , vj )}
est consistant.
...
k-consistance : considérer les valeurs d’une variable par
rapport à la combinaison de k-1 valeurs des autres variables.
N.B. : Un CSP arc-consisant ne pocéde pas forcemment une solution.(Exemple)
Imade Benelallam La Programmation Par Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Techniques de propagation de contraintes (1)

principe

Forward-checking et Look-ahead
Combinaison du filtrage et du retour-arrière : filtrage au cours
de la résolution
Forward-checking : Après chaque affectation d’une varible Xi ,
filtrer le domaine de la variable Xj non encore affectées dont
les valeurs violent les contraintes contenant Xi et Xj .
Look-ahead : Après chaque affectation d’une varible Xi , filtrer
le domaine de toutes les variable non encore affectées dont les
valeurs violent les contraintes contenant Xi et ces variables.

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Techniques de propagation de contraintes (2)

consistance de noeud

Un CSP (X , D, C , R) est consistant de noeud si pour toute

variable Xi de X , et pour toute valeur v de Di , l’affectation
partielle {(Xi , v )} satisfait toutes les contraintes unaires de C .

principe : anticipation + consistance de noeud

anticipation d’une étape l’affectation

pour chaque variable Xi non affectée dans A, on enlève de Di
toute valeur v telle que A ∪ {(Xi , v )} est inconsistante.

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Algorithme anticipation : forward-checking

fonction FC(A,(X,D,C)) : booléen
début
si (toutes les variables de X sont affectées) alors
retourner VRAI
sinon
choisir une variable Xi de X qui n’est pas encore affectée
pour (toute valeur Vi appartenant à Di ) faire
pour (toute variable Xj de X qui n’est pas encore affectée ) faire
Dj0 ← {Vj élèment de Dj | A ∪{(Xi , Vi ), (Xj , Vj )} est consistante}
si (Dj0 est vide) alors
retourner FAUX
finsi
finpour
si (FC(A ∪{(Xi , Vi )},(X, D’,C))= VRAI) alors
retourner VRAI
finsi
finpour
retourner FAUX
finsi
fin
Imade Benelallam La Programmation Par Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Algorithme Anticipation : FC

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Techniques de propagation de contraintes

consistance d’arc

Un CSP (X , D, C , R) est consistant d’arc si tout couple de

variables (Xi , Xj ) de X, et pour toute valeur vi de Di , il existe une
valeur vj appartenant Dj telle que l’affectation partielle
{(Xi , vi ), (Xj , vj )} satisfasse toutes les contraintes binaires de C.
principe : anticipation + consistance d’arc

anticipation d’une étape l’affectation

pour chaque variable Xi non affectée dans A, on enlève de Di
toute valeur vi telle qu’il existe une variable Xj non affectée
pour laquelle, pour toute valeur vj de Dj , l’affectation A
∪{(Xi , vi ), (Xj , vj )} est inconsistante.
Imade Benelallam La Programmation Par Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Algorithme Look-ahead : LH

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Comparaison des techniques de propagation

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Backjumping : BJ (1)

Le but du BJ est d’identifier la variable ayant causé

l’inconsistance.
Il enregistre de l’information durant la génération des
sous-séquences d’instanciation , puis l’utilise pour déterminer
la variable coupable de la situation d’inconsistance.
Dans le BJ,au cas ou on ne peut pas instancier une variable ,
on retourne à la variable la plus récemment instanciée et en
conflit avec la variable courante.

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Backjumping : BJ (2)
consistent← false;
maxCheck[i]← 0 ;
foreach x ∈ domaine[i] do
consistent← true;
v[i]← x;
foreach h ∈ (1 .. i-1) do
while consistent do
consistent← (check(v[i],v[h]);
maxCheck← max(h,maxCheck[i]);

if !(consistent) then
delete(x,domain[i]);
Algorithme 1 : Pseudo code du BJ

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Conflict directed backjumping (1)

Le CBJ choisira de revenir vers la variable Xj la plus

récemment affectée et appartenant à l’ensemble de conflit de
Xi.
dans le cas ou Xj n’a pas d’autres valeurs
possibles,l’algorithme retournera vers la variable Xk la plus
récemment affectée appartenant à l’ensemble de conflit de Xi
et Xj.

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Conflict directed backjumping (2)

consistent← false;
confSet[i]← {0} ;
foreach x ∈ domaine[i] do
consistent← true;
v[i]← x;
foreach h ∈ (1 .. i-1) do
while consistent do
consistent← (check(v[i],v[h]);
if !(consistent) then
confSet[i]← confSet[i] ∪{h} ;

if !(consistent) then
delete(x,domain[i]);
Algorithme 2 : Pseudo code du CBJ
Imade Benelallam La Programmation Par Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Dynamic backtracking (1)

Le DBT utilise la notion des nogoods : pour un problème

P=(X,D,C) ,un nogood est un sous ensemble de
l’instanciation courante responsable de l’impasse.
Le DBT, tout comme le CBJ, choisit la variable la plus
récente dans le nogood(l’ensemble de conflict de CBJ) afin de
défaire l’affectation.
Il ne suprime que l’information dépendante de cette
affectation (pas celles des affectations d’après) : l’information
utile est conservée.Ceci conduit à ce que l’ordre des
affectations des variables soit changeable.

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Dynamic backtracking (2)

dbt(A)
if A complète then
if A solution then
Fin;
else
soit n le nogood associé à une contrainte violée
dbt-Retour(A,n);
else
Soit X non istancié if ∃ Xi tq N(Xi)= n∅ then
dbt(A ∪ X=i);
else
n= ∨ N(Xi);
dbt-Retour(A,n);

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Dynamic backtracking (3)

dbt-Retour(A,n) if l’affectation de n est vide then

FIN;
else
soit Yi instancié tq @ variable de l’affectation de n > à y
met-à-jour(A,n,Yi);
A← A- {Y=j};
dbt(A);
met-à-jour, à chaque retour-arrière, assure que les nogoods N(Xi)
sont détruits dès qu’une variable de leur affectation change de
valeur.
Algorithme 3 : Pseudo code du DBT

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Heuristiques : paramétrage des algorithmes

Dans les algorithmes présentés, il y a des choses qui ne sont

pas précisées :
dans quel ordre on instancie les variables ;
dans quel ordre on prend les valeurs ;
quelle consistance locale on maintient.
Ces décisions (appelées heuristiques ) sont extrêmement
importantes pour l’efficacité de l’algorithme.
Si on s’engouffre dans une branche sans solutions, on peut
passer énormément de temps avant de s’en apercevoir.
Les premières décisions sont particulièrement importants
(quand on en haut de l’arbre de recherche).

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Types d’ heuristiques

Il y en a deux types :
Statiques : l’ordre est fixée avant commencer l’algorithme.
Dynamiques : l’ordre peut varier pendant l’algorithme.
Les heuristiques statiques sont basées sur des propriétés du
graphe de contraintes du problème,

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Heuristiques

Choix de variables
MinDomain (Statique)
MaxConstraint (Statique)
Dom over deg = taille dom / nombre de contraintes
(Dynamique)
Choix de valeurs
minVal (Statique)
maxVal (Statique)
minConf (Statique)
minConf (Statique)

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Choco solver : un peu d’histoire

1999 : a first CLAIRE implementation within the OCRE

project an national initiative for an open constraint solver for
both teaching and research (Nantes, Montpellier, Toulouse,
Bouygues, ONERA)
2003 : a first Java implementation portability, ease of use for
newcomers, etc.
2008 : Choco V2 a clear separation between the model and
the solving machinery ; a complete re-factoring ; a
user-oriented version

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Choco solver : usage industriel

Big companies : Bouygues, Amadeus, Dassault

Research agencies : ONERA, NASA
Software and Integrators : Kls-Optim, alfaplan GmbH

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Choco solver : architecture à deux niveaux

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Choco solver : variables et contraintes

A wide variety of variable paradigms :

Integer variables, Set variables, Real variables, Composite
variables
About 70 available constraints :
Classical arithmetic constraints : equal, not equal, less or
equal, greater or equal,
A large set of useful global constraints : AllDifferent and
BoundAllDifferent, GlobalCardinality and BoundGCC,
AtMostNvalue, Cumulative, Occurence, Element, . . .

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Choco solver : stratégies de recherche

User can use predefined search methods :

1 Searching CSP solutions : solve for searching first solution and
solveAll for searching all solutions
2 Optimizing a problem by maximizing ou minimizing a variable
value (maximize and minimize) with or without restart
3 Some new feature in next release like solve with restarts
(useful for heuristics with learning). . .

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Choco solver : Heuristiques

Choco proposes a set of implemented Search Heuristics. Two kinds

are distinguished :
1 Variable choice : MinDomain, RandomIntVarSelector,
StaticVarOrder, DomOverDeg, DomOverDynDeg,
DomOverWDeg, DomOverFailureDeg, LexIntVarSelector, . . .
2 Value choice for a Variable : DecreasingDomain,
IncreasingDomain, MaxVal, MinVal, MidVal,
RealIncreasingDomain, RandomIntValSelector,
RandomSetValSelector, . . .

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Choco solver : démarche de résolution

Pour les programmes Choco que nous verrons, les imports suivants
sont nécessaire :
import static choco.Choco.*;
import choco.kernel.model.variables.integer.IntegerVariable;
import choco.Choco;
import choco.cp.model.CPModel;
import choco.kernel.model.Model;
import choco.kernel.model.constraints.Constraint;
import choco.kernel.solver.Solver;
import choco.cp.solver.CPSolver;

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Choco solver : démarche de résolution

Dans Choco, on construit un modèle puis on créé et on utilise un
solveur pour résoudre le problème. Pour créer le modèle :
Model m = new CPModel();
Dans tous les exemples et exercices nous utiliserons des variables
entiéres, dont le type Choco est IntegerVariable. Pour créer une
variable entiére, on utilise la méthode :
Choco.makeIntVar(String name, int min, int max);
qui prend une chaı̂ne de caractère qui sera le nom de la variable et
deux entiers qui sont les bornes de son domaine. Par exemple :
IntegerVariable S = Choco.makeIntVar("S",0,9);
Une fois une variable créer, on peut l’ajouter au modèle :
m.addVariable(S);
Imade Benelallam La Programmation Par Contraintes
 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Choco solver : démarche de résolution

Les contraintes sont de type Constraint. On les construit à partir

des variables, puis on les ajoute au modèle avec la méthode
addConstraint. Par exemple une contrainte X + Y ≺ 10 :
Model m = new CPModel();
IntegerVariable X = /* ... */
IntegerVariable Y = /* ... */
m.addVariable(X);
m.addVariable(Y);
Constraint c = lt(plus(X,Y),10);
m.addConstraint(c);

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Choco solver : démarche de résolution

Il reste alors à créer le solveur et l’utiliser sur le modéle :

// Creation du solveur
Solver s = new CPSolver();
// Lecture du modele
s.read(m);
// Resolution du modele
s.solve();
On peut avoir le nombre de solutions par la méthode : int
getNbSolutions();
de la classe Solver On peut récupérer les variables et leurs solutions
éventuelles avec la méthode getVar de la classe Solve, qui prend en
argument une variable préalablement ajoutée au modèle qui a été
résolu. Par exemple : System.out.println(s.getVar(X));

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Choco solver : Exemple (SEND + MORE = MONEY)

import static choco.Choco.*;

import choco.kernel.model.variables.integer.IntegerVariable;
import choco.Choco;
import choco.cp.model.CPModel;
import choco.kernel.model.Model;
import choco.kernel.model.constraints.Constraint;
import choco.kernel.solver.Solver;
import choco.cp.solver.CPSolver;
class Sendmoremoney{
public static void main(String [] argv){

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Choco solver : Exemple (SEND + MORE = MONEY)

// Creation du modele
Model m = new CPModel();
// Creation et ajout des variables et de leurs domaines
int numberOfVariables = 8;
IntegerVariable [] variable =
new IntegerVariable[numberOfVariables];
String [] name = {"S","E","N","D","M","O","R","Y"};
for(int i=0; i<numberOfVariables; i++){
variable[i] = Choco.makeIntVar(name[i],0,9);
m.addVariable(variable[i]);
}

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Choco solver : Exemple (SEND + MORE = MONEY)

// Creation et ajout des contraintes:

// 1. S et M ne doivent pas etre 0
m.addConstraint(Choco.neq(variable[0],0));
m.addConstraint(Choco.neq(variable[4],0));
// 2. Toutes les variables doivent etre differentes
for (int i = 0; i < numberOfVariables; i++){
for (int j = i + 1; j < numberOfVariables; j++){
Constraint c = Choco.neq(variable[i],variable[j]);
m.addConstraint(c);
}
}

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Choco solver : Exemple (SEND + MORE = MONEY)

// 3. On doit avoir SEND+MORE = MONEY Constraint c =

Choco.eq(plus(mult(1000,variable[0]),
plus(mult(100,variable[1]),
plus(mult(10,variable[2]),
plus(variable[3],
plus(mult(1000,variable[4]),
plus(mult(100,variable[5]),
plus(mult(10,variable[6]),
variable[1]))))))),
plus(mult(10000,variable[4]),
plus(mult(1000,variable[5]),
plus(mult(100,variable[2]),
plus(mult(10,variable[1]),
variable[7])))));
m.addConstraint(c);

Imade Benelallam La Programmation Par Contraintes

 Définition
Modélisation
Introduction à la PPC
Résolution
Les CSPs
Graphe de contraintes
Les CSPs distribués
Algorithmes de résolution
TP : Solveurs Choco

Choco solver : Exemple (SEND + MORE = MONEY)

// Creation du solveur
Solver s = new CPSolver();
// Lecture du modele
s.read(m);
// Resolution du modele
s.solve();
// Affichage des solutions
for(int i=0; i<numberOfVariables; i++)
System.out.println(s.getVar(variable[i]));
}
}

Imade Benelallam La Programmation Par Contraintes

 Introduction à la PPC Définition
Les CSPs Approche Synchrone : SBT
Les CSPs distribués Approche Asynchrone : ABT

Définition d’un DisCSP

Un DisCSP se définit comme {A, X , D, C, ϕ}

A = {A1 ,. . ., Ak } un ensemble ordonné d’agents.
X = {x1 , . . . , xn } est un ensemble de n variables.
D = {D(x1 ), . . . , D(xn )} est un ensemble de domaines D(xi ).
C = {C1 , C2 , . . . , Ck } est l’ensemble des contraintes.
ϕ : X → A : une fonction de mapping.
x1 Agent1 Agent2
x4

nt Co nstraint
x2 x3 x6
Inter-Age
x5

x7 x8
Intra-Agent Constraint Agent3
x10 x9

Imade Benelallam La Programmation Par Contraintes

 Introduction à la PPC Définition
Les CSPs Approche Synchrone : SBT
Les CSPs distribués Approche Asynchrone : ABT

Approche Synchrone : SBT

Principes
Similaire à la recherche centralisée ;
Privilège transitoire à travers les agents ;
Seul l’agent ayant le privilège peut instancier une valeur ou
faire du backtrack.

x1 x2 x3 xn
cpa

x1 = v1 , x2 = v2

Imade Benelallam La Programmation Par Contraintes

 Introduction à la PPC Définition
Les CSPs Approche Synchrone : SBT
Les CSPs distribués Approche Asynchrone : ABT

Approche Asynchrone : ABT [Yokoo et al. 1992]

Principes
Les agents travaillent en parallèle ;
Les contraintes sont orientées ;
Un ordre total est défini entre les agents ;
{1, 2} {2}

x1 x2

6= 6=
ok?(x1 = 1) 2)⇒ x2 6= 2)
ok?(x12 = 1
ngd(x
{1, 2}

x3

AgentView
AgentView
:(x1 :(x
= 11,=x21)= 2)
x1 = 1 ⇒ x2 6= 2

Imade Benelallam La Programmation Par Contraintes

 Introduction à la PPC Définition
Les CSPs Approche Synchrone : SBT
Les CSPs distribués Approche Asynchrone : ABT

Approche Asynchrone : ABT [Yokoo et al. 1992]

Principes
Les agents travaillent en parallèle ;
Les contraintes sont orientées ;
Un ordre total est défini entre les agents ;
{1, 2} {2}

x1 x2

6= 6=
ngd(x1 = 1 ⇒ x2 6= 2)
{1, 2}

x3

AgentView :(x1 = 1)
x1 = 1 ⇒ x2 6= 2

Imade Benelallam La Programmation Par Contraintes