Introduction à la programmation par
contraintes
Table des matières
Généralités.
Modélisation avec la programmation par contraintes.
Stratégie de recherche dans la programmation par
contraintes.
Programmation par contraintes en utilisant COMET
Généralités
Deux contributions importantes de la programmation
par contraintes.
Une approche appliquée aux problèmes combinatoires
Complémentaire aux autres techniques classiques
de la recherche opérationnelle.
Faisabilité vs optimalité.
- Un langage d'optimisation combinatoire.
Langage riche (raisonnement par block).
Langage de stratégie de recherche par procédure.
La Programmation Par contraintes (PPC) combine un
raisonnement par contraintes et une stratégie de
recherche.
Généralités
PPC = Réduction de domaines + Recherche
Réduction de domaines = Élimination des
valeurs des solutions non réalisables.
Recherche = L'exploration systématique de
l'espace de solutions.
Généralités
Branchement et réduction de domaines.
● Réduction de domaines : réduire l'espace de
recherche le plus possible.
● Branchement : Lorsque la réduction de domaines
n'est plus possible, on décompose le problème en
plusieurs sous-problèmes.
Questions fondamentales.
● Comment assurer la réduction des domaines ?
● Comment assurer la décomposition ou le branchement ?
Généralités
Réduction de domaines.
● On représente explicitement le domaine de recherche
de chaque variable.
● On utilise les contraintes pour la réduction de
domaines.
Contrainte
Domain store
Généralités
Un langage de PPC est présente générale-
ment :
Des contraintes arithmétiques, logiques, …
Des contraintes globales.
Une procédure de recherche permettant de définir
l'arbre de recherche + la stratégie d'exploration de
l'arbre.
Une séparation entre la modélisation et la procédure
de recherche.
Introduction à Programmation par
contraintes
Domaine Contrainte
Pour chaque variable, Capture une structure in-
quel est l'ensemble téressante du pro-
des valeurs possibles. blème.
Si une variable a un do- Besoin de déterminer :
maine vide alors, le Si la contrainte est réali-
problème est non réa- sable ou non avec les
domaines des va-
lisable. riables associées.
Si le domaine de chaque Aussi, il faut éliminer les
variable est un single- valeurs impossibles
ton alors, une solution des variables asso-
est trouvée. ciées.
Introduction à la programmation par
contraintes
Les LP variables approximent les variables
mathématiques ayant un domaine infini.
Comme pour les variables de certains pro-
blèmes en nombres entiers, les variables de
la programmation par contraintes doivent
avoir un domaine fini.
Introduction à la programmation par
contraintes
A quoi sert une contrainte :
- Vérifier la faisabilité : Est ce que avec les
domaines des variables la contrainte est satis-
faite.
- Réduction des domaines : retirer les va-
leurs des domaines si elles n'apparaissent pas
dans au moins une solution
Exemple : Série Magique
Une série S (S0,...,Sn) est dite Magique si et
seulement si : pour tout j, Sj est le nombre
d'occurrence de j dans S.
0 1 2 3 4
? ? ? ? ?
Exemple : Série Magique
0 1 2 3 4
2 1 2 0 0
Exemple : Série Magique
int n = 5;
range D = 0..n-1;
var<CP>{int} s[D](cp,D);
solve<cp> {
Reification
forall(k in D)
[Link](s[k] == sum(i in D) (s[i]==k));
}
Permettre l'utilisation d'une contrainte dans une autre
contrainte.
Remplacer une contrainte par une variable 0/1représentant si
la contrainte est vraie ou non.
Exemple : Mariage Stable
Exemple : Mariage Stable
Éléments de contraintes :
Possibilité d'indexer un vecteur ou une matrice par une va-
riable de décision
Contraintes logiques :
Possibilité d'utiliser une combinaison de contraintes lo-
giques.
Deux types de contraintes :
Si John est marié à Jane, alors Jane doit être mariée à
John.
Le mari de la femme de George est George.
Exemple : Mariage Stable
explore<cp> {
forall(i in Men)
[Link](husband[wife[i]] == i);
forall(i in Women)
[Link](wife[husband[i]] == i);
forall(i in Men,j in Women)
[Link](preferm[i,j] > preferm[i,wife[i]] =>
preferw[j,husband[j]] > preferw[j,i]);
forall(i in Men,j in Women)
[Link](preferw[j,i] < preferw[j,husband[j]] =>
preferm[i,wife[i]] < preferm[i,j]);
}
Élément de Contrainte
•
X : variable 3 4 5
•
Y : variable 0 1 2 3 4 5
[0] [1] [2] [3] [4] [5]
•
C : vecteur 3 4 5 5 4 3
•
Contrainte: X = C[Y]
•
X≠3
•
Y≠1&Y≠4
Élément de Contrainte
Facility
location: Le client c est affecté à un entrepôt i seule-
ment si l'entrepôt i est ouvert. (open[i]=1 if warehouse i is
open)
IP: x[c,i] = 1 si le client c est affecté à i
x[c,i] <= open[i]
CP: w[c] est l'entrepôt auquel est affecté le client c
open[w[c]] = 1; (not a 0,1 variable)
Algorithme du Fixpoint
Recherche d'une solution réalisable :
- Algorithme général (fixpoint)
+ Répéter :
* Sélectionner une contrainte c
- If c est non réalisable, retourner
qu'il y a pas de solutions
- Sinon appliquer un algorithme de
réduction pour c jusqu'à ce qu'
aucune valeur ne peut être retirée
Application du Fixpoint
Constraints
Constraint Store
X<Y Y<4
X ∈ {1,3,4,5} Y ∈ {3,4}
Application du Fixpoint
Constraints
Constraint Store
X<Y Y<4
X ∈ {1,3,4,5} Y ∈ {3,4}
Application du Fixpoint
Constraints
Constraint Store
X<Y Y<4
X ∈ {1,3} Y ∈ {3,4}
Application du Fixpoint
Constraints
Constraint Store
X<Y Y<4
X ∈ {1,3} Y ∈ {3}
Application du Fixpoint
Constraints
Constraint Store
X<Y Y<4
X ∈ {1,3} Y ∈ {3}
Application du Fixpoint
Constraints Constraint Store
X<Y Y<4
X ∈ {1} Y ∈ {3}
Propagation de contraintes
La propagation de contraintes permet de ré-
duire les domaines des variables, dans le
but d'accélérer le parcours de l'arbre de re-
cherche.
La propagation de contraintes consiste à mo-
difier le domaine des variables impliquées
dans la contrainte, dans le but de rétablir la
consistance. Plusieurs types de consis-
tances, plus ou moins fortes peuvent être
considérées.
Propagation et consistance
Specialized to each constraint type:
3x+10y+2z + 4w = 4
x in {0,1}, y in {0,1,2}, z in {0,1,2}, w in {0,1}
Simple bound reasoning (Bound Consistency), that reasoning
on intervals of continuous values, gives
x in {0,1}, y in {0}, z in {0,1,2}, w in {0,1}
Domain reasoning (Domain Consistency) gives :
x in {0}, y in {0}, z in {0,2}, w in {0,1}
Consistance de domaine
Domain-consistency
Est la base de la PPC.
Une contrainte est dite domain-consistent si, pour
toute variable x impliquée et toute valeur du do-
maine de x, il existe des valeurs dans le domaine
des autres variables impliquées tel que la
contrainte est satisfaite.
Propagation et consistance
La PPC peut être vue sous forme de graphe où :
Les variables et les contraintes représentent les
sommets du graphe.
Les arcs connectent les variables et les contraintes.
Toute modification de domaine peut déclencher de
nouvelles réduction par propagation.
Domain Consistency
Les nœuds associés aux contraintes assurent ¨the domain
consistency¨.
Ils garantissent que les domaines de leurs variables liées
contiennent encore des valeurs compatibles avec la
contrainte.
Les contraintes ne doivent pas déclencher toutes les réduc-
tions de domaines. La plupart des contraintes arithmétiques
ne se propagent que le min et max des domaines.
Le processus s'arrête, soit à un point fixe (succès) ou génère
un domaine vide (échec).
Propagation et consistance
Du fait que les variables et les contraintes re-
présentent les sommets du graph-constraint,
la consistance de domaine est appelée
consistance par arcs.
Les solveurs de la PPC offrent plusieurs algo-
rithmes permettant d'assurer la consistance par
arcs (Arc consistency).
Domain Consistency Does Not Imply
Consistency
Soit x, y et z trois variables tel que :
var int x in 1..2 ;
var int y in 1..2 ;
var int z in 1..2 ;
L'ensemble des contraintes {x<>y, y<>z, z<>x} est arc
consistent, mais n'admet pas de solution.
Constraint Solving Algorithm
Dans les années 90, plusieurs algorithmes ont été déve-
loppés dans le but d'assurer Domain consistency (Arc
consistency).
Actuellement, cet aspect est bien maîtrisé, la recherche
scientifique se concentre sur le développement de
contraintes globales et de stratégie de recherche.
Coloriage de carte
● Colorier une partie de la carte géographique
de l'Europe : Belgique, Denmark, Pays-Bas,
France, Allemagne, Luxembourg.
● Deux pays ayant frontalier doivent avoir deux
couleurs différentes.
● Le but est de minimiser le nombre utilisé de
couleurs.
Coloriage de carte
Objective
enum Countries = Function
{Belgium,Denmark,France,Germany,Netherlands,Luxembourg};
var<CP> color[Countries](cp,1..4);
minimize<cp>
max(c in Countries) color[c]
subject to {
[Link](color[France] != color[Belgium]);
[Link](color[France] != color[Luxembourg]);
[Link](color[France] != color[Germany]);
[Link](color[Luxembourg] != color[Germany]);
[Link](color[Luxembourg] != color[Belgium]);
…
}
Exemple : Coloriage
●Color a map of (part of) Europe: Belgium,
Denmark, France, Germany, Netherlands, De
Luxembourg n
Ned
Use at most 4 colors
●
B
el Germ
L
u any
x
Franc
e
Exemple : coloriage
Denmark
Nederla
nd
Belgiu
m Germa
Lu
x
ny
France
Exemple : Coloriage
Denmark
Nederland
Belgium
Germany
Lux
France
Exemple : coloriage
Denmark
Nederland
Belgium
Germany
Lux
France
Exemple : coloriage
Denmark
Nederland
Belgium
Germany
Lux
France
Exemple : coloriage
Denmark
Nederland
Belgium
Germany
Lux
France
Exemple : coloriage
Denmark
Nederland
Belgium
Germany
Lux
France
Modélisation avec la PPC
Contraintes globales
Contraintes redondantes
Symétrie
Sudoku
Sudoko
combinatorial array
range R = 1..9; constraint comprehension
var<CP>{int} S[R,R](cp,R);
explore<cp> {
// constraints for fixed positions
forall(i in R)
[Link](alldifferent(all(j in R) S[i,j]),onDomains);
forall(j in R)
[Link](alldifferent(all(i in R) S[i,j]),onDomains);
forall(i in 0..2,j in 0..2)
[Link](alldifferent(all(r in i*3+1..i*3+3,
c in j*3+1..j*3+3)S[r,c]),
onDomains);
}
Contraintes globales
Reconnaître certaines structures combina-
toires qui apparaissent dans de nombreuses
applications pratiques.
alldifferent est une contrainte globale fonda-
mentale qu'on retrouve dans plusieurs situa-
tions.
Faciliter la modélisation en la rendant natu-
relle et déclarative.
Alldifferent Contrainte Globale
•
Most well-known global constraint.
alldifferent(x,y,z)
states that x, y, and z take on different values.
So x=2, y=1, z=3 would be ok, but not x=1, y=3, z=1.
•
Very useful in many resource allocation, time tabling,
sport scheduling problems
Alldifferent Contrainte Globale
Alldifferent: Feasibility
Faisabilité ? Étant donné les domaines des
variables
Création domaine/variable (graphe bipartie)
Trouver un couplage maximum
x1
1
x2 2
x3 3
x4 4
x5 5
Alldifferent : Pruning
C'estl'avantage de la modélisation par
contraintes globales.
Pruning (élagage) consiste à limiter le déve-
loppement de l'arbre de recherche.
x1 1
x2 2
x3 3
x4 4
5
x5
Contraintes Globales
Plusieurscontraintes globales ont été déve-
loppées :
cardinality( card, value, base) : le nombre de fois que va-
lue[i] apparaît dans le vecteur base est card[i].
circuit(succ) : la valeur du vecteur succ forme a hamilto-
nian circuit (il faudrait suivre la séquence, 1, succ[1],
succ[succ[1]], et ainsi de suite).
Euler Knight
Applications :
Utiliser le cheval pour visiter tous les cases d'un échiquier
exactement une seule.
Utiliser aussi dans la modélisation du TSP (problème du
voyageur de commerce).
Utiliser aussi dans la modélisation de toutes les variantes
du VRP.
Euler Knight
range Chessboard = 1..64;
var<CP>{int} jump[i in Chessboard](cp,Knightmoves(i));
solve<cp>
[Link](circuit(jump));
function set{int} Knightmoves(int i) {
set{int} S;
if (i % 8 == 1)
S = {i-15,i-6,i+10,i+17};
else if (i % 8 == 2)
S = {i-17,i-15,i-6,i+10,i+15,i+17};
else if (i % 8 == 7)
S = {i-17,i-15,i-10,i+6,i+15,i+17};
else if (i % 8 == 0)
S = {i-17,i-10,i+6,i+15};
else
S = {i-17,i-15,i-10,i-6,i+6,i+10,i+15,i+17};
return filter(v in S) (v >= 1 && v <= 64);
}
Contraintes Redondantes
Bin Packing Problem
import cotfd;
range Items = 1..16;
range Bins = 1..6;
int capa =8;
int weight [Items] = [1,1,2,2,2,2,2,3,3,3,3,4,4,5,5,6];
Placement
of each
Solver<CP> cp(); Item
var<CP>{int} x[Items](cp,Bins);
var<CP>{int} load[Bins](cp,0..capa); Load of
each Bin
Bin Packing Problem
Solver<CP> cp();
var<CP>{int} x[Items](cp,Bins);
var<CP>{int} load[Bins](cp,0..capa);
solve<cp>{
forall(b in Bins){
[Link](load[b] == sum(i in Items) (x[i]==b)*weight[i]);
}
}using{
label(x);
}
cout << [Link]() << endl;
2210 Failures
Bin Packing Problem
Solver<CP> cp(); Redundant
var<CP>{int} x[Items](cp,Bins); Constraint
var<CP>{int} load[Bins](cp,0..capa);
solve<cp>{
forall(b in Bins){
[Link](load[b] == sum(i in Items) (x[i]==b)*weight[i]);
}
[Link](sum(b in Bins) load[b] == sum(i in Items) weight[i]);
}using{
label(x); Only 85
} Failures
cout << [Link]() << endl;
Modèle PPC
Les contraintes communiquent à travers les
domaines.
Constaints Domain
Domain store
store
Redundant Constraint.
Improves
communication
Contrainte Redondante
Rôle 1
Exprimer une propriété de la solution.
Booster la propagation des autres contraintes.
Rôle 2
Offrir une vue globale sur le problème.
Combiner les contraintes existantes.
Améliorer la communication.
Rôle 3
Représenter une conséquence des contraintes existantes.
Bin Packing : Contrainte Globale
Solver<CP> cp(); Only 1
var<CP>{int} x[Items](cp,Bins); Failures
var<CP>{int} load[Bins](cp,0..capa);
solve<cp>{
[Link](multiknapsack(x,weight,load));
}using{
label(x);
}
cout << [Link]() << endl;
Stronger pruning that:
orall(b in Bins){
[Link](load[b] == sum(i in Items) (x[i]==b)*weight[i]);
Modèle PPC
Constraint Store
Domain store
Global
Constraint
Symétrie
Plusieurs problèmes possèdent naturellement
de la symétrie.
Explorer les solutions symétriques est plus qu'utile.
Plusieurs sortes de symétrie
Symétrie de variables
Symétrie de valeurs
Nous pouvons éliminer la symétrie soit au ni-
veau de modélisation soit au niveau de la
recherche.
Sport Scheduling Problem
int n = 14;
range Periods = 1..n/2;
range Teams = 1..n;
range Weeks = 1..n-1;
range EWeeks = 1..n;
enum Location = {home,away};
range Games = 1..(n/2)*n-1;
tuple triple {int a1; int a2; int a3; }
set{triple} Triples();
forall(i in 1..n,j in 1..n: i < j)
[Link](triple(i,j,(i-1)*n + j));
Table<CP> t( all(e in Triples) e.a1,
all(e in Triples) e.a2,
all(e in Triples) e.a3);
Sport Scheduling Problem
var<CP>{int} team[Periods,EWeeks,Location](m,Teams);
var<CP>{int} game[Periods,Weeks](cp,1..n^2);
explore<cp>{
forall(w in EWeeks)
[Link](alldifferent(all(p in Periods,l in Location) team[p,w,l]));
forall(p in Periods)
[Link](exactly(all(i in Teams)2,all(w in EWeeks,l in Location) team[p,w,l]));
[Link](alldifferent(all(p in Periods,w in Weeks) game[p,w]));
forall(p in Periods,w in Weeks)
[Link](table(team[p,w,home],team[p,w,away],game[p,w],t));
forall(p in Periods, w in Weeks)
[Link](team[p,w,home] < team[p,w,away]);
}
La stratégie de recherche en PPC
Stratégie de recherche et propagation
La propagation réduit la taille de l'arbre de recherche à
chaque nœud de branchement.
La propagation permet de déterminer assez rapidement
l'infeasibility
Aussi en réduisant les domaines des variables nous sim-
plifions le choix variable-valeur
Branching on V
Real search space
Heuristiques de recherche
La plupart des solveurs fournissent des stratégies de
recherche par défaut.
Cependant, il est recommandé de développer sa
propre stratégie de recherche pour les problèmes
complexes.
Dans les dernières années, plusieurs chercheurs se
sont penchés sur le développement de méthodes
de recherche puissantes. (Voir Pesant et al.
(2007)). Real search space
Real search space
Heuristiques de recherche
N'importe quelle heuristique qui permet d'at-
teindre rapidement une solution réalisable
est VALIDE.
Cependant, changer l'heuristique de re-
cherche ne doit pas changer la forme de
l'arbre de recherche
Changing the heuristic
First solution First solution
Problème d'optimisation
Pour trouver la solution optimale d'un pro-
blème d'optimisation, il faudrait explorer la
totalité de l'arbre de recherche.
Typiquement, à chaque fois qu'une solution
est trouvée, une contrainte est ajoutée au
modèle forçant la prochaine solution à être
meilleure. not explored because
cost > cost(s)
Problème d'optimisation
Il est très utile d'avoir une borne supérieure
de l'objectif (cut région A)
Il est aussi important d'avoir une borne infé-
rieure de l'objectif (cut région B)
A
Branchement
Lorsque l'algorithme ¨Constraint Solving¨est
appliqué, on applique la méthode de re-
cherche suivante :
Choose a variable x with non-singleton domain
(d1, d2, … di)
For each d in (d1, d2, … di)
add constraint x=di to problem
X=d1 X=d2 X=d3 X=d4
Procédure de recherche classique
Variable/Value (labeling)
Deux étapes :
Choix de la variable dont on doit assigner une valeur.
Choix de la valeur à assigner.
Ordre dynamique
Choix de la prochaine variable dynamiquement.
Choix de la prochaine valeur dynamiquement.
Variable/Value (labeling)
Choix de la variable
Often the most constrained variable (first fail : smallest
domain for queen problem, largest item in Bin Packing)
Choix de la valeur
Often a value that decreases the solution space the least
S'il y a pas de solutions dans le reste de la
branche de l'arbre il vaut mieux le savoir le
plus tôt possible ceci est l'idée derrière the
first fail stratégie.
Problème des Reines
using {
forall(c in C: !row[c].bound())
by (row[c].getSize())
tryall<cp>(r in R: row[c].memberOf(r))
by (col[r].getSize())
[Link](row[c] == r);
}
Domain Splitting
Motivation
Dans certains cas la stratégie du labeling peut engendrer
des erreurs et par conséquence des temps de calcul
très élevés.
Domain Splitting
Consiste à partitionner le domaine d'une variable.
The Magic Square Problem
All numbers are different
The sum on all rows 2 9 4
=
The sum on all columns
7 5 3
= 6 1 8
The sum on the
diagonalss
The Magic Square Problem
1 90 18 14 119 112 117 118 20 54 8
93 2 99 16 29 92 94 31 68 56 91
39 75 3 5 12 87 95 101 57 97 100
21 83 103 4 86 78 84 58 89 15 50
79 70 98 107 55 51 59 28 25 76 23
24 106 63 32 109 60 9 108 104 34 22
69 49 105 110 61 26 82 7 13 72 77
73 46 102 62 40 36 38 113 81 33 47
71 42 64 114 41 27 44 53 115 52 48
80 65 6 111 74 67 19 37 11 116 85
121 43 10 96 45 35 30 17 88 66 120
The Magic Square Model
range R= 1..n; range D= 1..n^2; int T=n*(n^2+1)/2;
var<CP>{int} s[R,R](cp,D);
explore<cp> {
forall(i in R) {
[Link](sum(j in R) s[i,j] == T);
[Link](sum(j in R) s[j,i] == T);
}
[Link](sum(i in R) s[i,i] == T);
[Link](sum(i in R) s[i,n-i+1] == T);
[Link](alldifferent(all(i in R,j in R) s[i,j]));
forall(i in 1..n-1) {
[Link](s[i,i] < s[i+1,i+1]);
[Link](s[i,n-i+1] < s[i+1,n-i]);
}
The Magic Square Search
using {
var<CP>{int}[] x = all(i in R,j in R) s[i,j];
range V = [Link]();
while (!bound(x)) {
selectMin(i in V:!x[i].bound())(x[i].getSize()) {
int mid = (x[i].getMin()+x[i].getMax())/2;
try<cp>
[Link](x[i] <= mid);
|
[Link](x[i] > mid);
}
}
}
Introduction à Comet
Types de données
Nombres entiers
Nombres rationnels et réels
Booléens
Chaîne de caractère (Strings)
….
Introduction à Comet
Types de données avancés
Range (range dom 0..10)
Vecteurs (One Dimensional Arrays)
Int tab[1..3] = [4,5,12] ;
Matrices (Multi Dimensional Arrays)
Int mat[1..3,2..3] = [[1, 2], [3,6], [4,4]] ;
...
Introduction à Comet
Contrôle
Instructions de contrôle
If else
Switch
For (int i = 2 ; i < 5 ; i++)
Do while
While
forall
Introduction à Comet
Sélection
Select : selects a random element.
SelectMin : selects minimum element according to an eva-
luation function.
SelecMax : selects maximum element according to an eva-
luation function.
SelectPr : selects an element according to a probability
distribution.
SelectFirst : selects the lexicographically smallest element.
SelectCircular : selector with a state ; successive execu-
tions consider elements in a circular way.
Introduction à Comet
Function
Function int factorial(int n)
{ if(n == 1) return 1 ;
Else
Returne factorial(n-1)*n ; }
Introduction à Comet
Structure
Tuple pair{int a ; int b ;}
Pair p(2,3) ;
Cout << p << endl ;
Cout << p.b << endl ;
pair<a=2,b=3>
3
Introduction à Comet
Solveurs de Comet
Un solveur CP (programmation par contraintes)
Un solveur LP (programmation linéaire)
Un solveur MIP (programmation linéaire en
nombres entiers)
Un solveur LS (recherche locale basée sur les
contraintes)
Introduction à Comet
Déclaration des solveurs
Import cotls ;
Solver<LS> ls() ;
Import cotln ;
Solver<LP> lp() ;
Import cotln ;
Solver<MIP> mip() ;
Import cotfd ;
Solver<CP> cp() ;
Introduction à Comet
Déclaration des variables
var{int} queen[Size](m,size):= [Link]() ;
var<LP>{float} cut[Size](lp) ;
var<MIP>{int} x[Size](mip,0..maxvalue) ;
var<CP>{int} queen[Size](cp, Size) ;
Introduction à Comet
Déclaration des contraintes
Constraint<LP> vect_const[Size] ;
forall(j in Size) vect_const[j] = [Link](sum(i in 1..10) y[i] <= 120) ;
ConstraintSystem<LS> Sys(m) ;
forall(i in Size)
forall(j in Size : j != i) [Link](queen[i] != queen[j]) ;
Solver<CP> cp() ;
[Link](alldifferent(queen)) ;
