Okay guys. 
You know, I talked about the language of 
constraint programming the last time and 
that I was presenting an overview of what 
it is. 
You know, I lied. 
Okay. 
So there is one more thing that I need 
about, that I need to talk to you about 
and this is global constraints. 
Okay? 
So global constraints are one really 
important feature of the language of 
constraint programming. 
They are part of this richness and the 
ability to express complex substructure, 
okay. 
They are a critical path of any 
constraint programming system and this is 
a very active, you know, research area in 
the field, okay. 
So, what is the global constraints? 
The global constraints capture the, the, 
the combinatorial substructure arising in 
many applications. 
So, the good analogy here. 
Is essentially Lego blocks. 
Okay? 
So you, when, when you buy Legos, you 
have a big set of pieces that are 
encapsulate things that you want to build 
from. 
Global constraints are exactly like that. 
They are capturing substructure that are, 
that are arising in a variety of 
application. 
And we can use them directly. 
We don't have to express them in terms of 
smaller blocks. 
Okay? 
They make modeling, you know, easier, 
they are more natural. 
They make the model easier to read, they 
make the model more concise. 
But, the real, real interesting aspect of 
them is also the fact that these 
combinatorial substructure are really 
given to the solver. 
We capture this structure and we give 
them, you know, directly to the solver. 
And then the solver has a lot of 
information to do interesting things. 
And in particular, it gives the solver 
the ability to use dedicated algorithm 
for each one of these substructure. 
So I'm going to give you examples. 
First, you know, I'm going to show you 
the modeling and then I'm going to tell 
you how these things can actually help 
you from a computational standpoint. 
So, what you see here is probably the 
most famous, you know, global 
constraints, the alldifferent 
constraints. 
And these constraints is basically saying 
that the variable x1 to xn have to be 
given a value, have to be given all 
different values. 
So no two variables in x1 and xn can, can 
take the same value. 
Okay? 
Now remember, you know, we had this 
beautiful queens example in the previous 
lectures? 
Okay? 
And what that was basically saying is 
that all these queens, okay, have to be 
placed on the chessboard. 
Such that they were not on the same row, 
the same upward diagonal and the same 
downward diagonal. 
Okay? 
Well, you can essentially express the 
same example with three constraints and 
that's what you see there, okay. 
Same decision variable but now instead of 
saying all these rows, you know, in which 
the, you know, the queens were placed, 
had to be, you know, pairwise different. 
You just specify one constraint which 
says all the rows have to be different. 
Okay. 
That's what you said. 
That's what you are stating there. 
Now, if you look at the other 
constraints, these guys, okay. 
So what you see once again is that, you 
know, you see row i plus i, row j plus j. 
Essentially what it is that you have a 
bunch of expression row i plus i row j 
plus j row k plus k and essentially all 
these things have to be different and 
that's what you express in this 
constraint. 
Okay? 
And so that's once again a-alldifferent 
constraints. 
Okay? 
And these all different constraints is 
going to capture the upper diagonal and 
you'll have the last alldifferent 
constraint which is going to capture the 
lower bound. 
Now you see that this operator all over 
there, essentially this is [INAUDIBLE] 
comprehension, okay. 
So essentially what it says is take all i 
in r, okay? 
Take the, the collection of expressions 
that you see over there, which is in this 
particular case, you know, row i plus i, 
and collect all these in an array, and 
then that's, that's the array that you 
have as a result, okay? 
In this particular case, this array's 
going to be passed to the alldifferent 
constraints, okay? 
So, essentially, this is collecting a 
bunch of things, and then saying that all 
these variables, or expression, in this 
particular case, have to be different. 
Okay, so in a sense we can express this 
screen problem with three constraints. 
Okay? 
Now why would we ever do that? 
It seems more complicated and so on but 
what I'm going to show you is that this 
has a lot of computational advantages. 
Okay, so let's look. 
You know, you know from now on from, you 
know, previous lecture that every 
constraints has two goals in life. 
The first goal is to, is to do 
feasibility testing. 
You want to know if the constraints is 
feasible. 
Okay? 
Remember we had a constraints. 
We have essentially for every one of the 
variables the domain. 
Okay, so that's a set of values that a 
variable can take. 
Okay? 
So, we often use this notation here, you 
know, this is a constraint and then we 
said that d1 is the domain of x, of x1 
and then d2 is the domain of x2 and so 
on. 
Okay? 
So, what is feasibility? 
Feasibility is finding a value in this 
domain such that when the variables are 
assigned it's variables the constraint is 
satisfied and that's essentially what 
this formula is basically telling you. 
Does there exist a value in the domain of 
x1? 
Okay? 
Such that, and there, there, such that if 
I, so that I can find another value for 
the you know, v2 in the domain of x2, and 
v3 in the domain of x3. 
Such that, when I assign all these values 
to the cons, to the variable of the 
constraint, the constraint is true. 
That's feasibility testing. 
Okay? 
Now, let's look at this constraint here, 
okay? 
So, we have the alldifferent, okay, which 
is on three variables, x1, x2, x3. 
You know, cannot be much simpler than 
that, okay? 
And then, for every one of these 
variable, okay, so, we have a domain. 
And in this particular case, three 
variables with a very simple domain, 
value 1 and value 2. 
Okay? 
Now, so in a sense, all different and 
then these other domains. 
Okay? 
Is this feasible? 
Okay. 
No, it's not. 
Okay. 
Why is not feasible.Okay. 
It's not feasible because we have three 
variables and we have two values. 
Okay? 
So people in computer science code, that 
the pigeon hole principle, I have never 
seen a pigeon in a hole but anyway. 
So this is the pigeon hole principle. 
Probably pigeons are looking for holes 
and if you have three pigeons and two 
holes, they can't all fit in the hole. 
Okay, in the holes. 
Okay, so is, in a sense here what it's 
telling you, three variables two value, 
impossible. 
You can't have feasibility. 
Right? 
So we know that the global constraints is 
going to say no, no, no, this is not 
feasible. 
Okay. 
Now, if we look at, you know, the first 
formulation that we had when we were 
using the queen's example we had 
essentially three constraints to express 
the same thing. 
Right? 
So we said x1 can not be equal to x2. 
X2 cannot be equal to x3 and that x3 
cannot be equal to x1. 
Now if you look at every one of these 
constraints independently. 
Okay. 
Do the same test that we just did for the 
that alldifferent. 
What do you get? 
Well. 
For the first constraint I can take the 
value 1 for x1 and the value 2 for X2 and 
this constraint is fine. 
It's satisfied. 
Okay. 
You look at the second constraint and you 
can do exactly the same trick. 
Of course this time is the value x2 and 
the value x3. 
Okay? 
But essentially it's true as well. 
And the third constraint is true as well. 
So all these constraints, when you look 
at them independently, they are fine. 
Okay? 
So, the system is going to say, yeah, you 
know, the set of constraints look 
satisfiable. 
Okay? 
Although we know for sure that they are 
not. 
Okay? 
So, that's one of the big impact of 
global constraints. 
Okay? 
They can actually detect infeasibility 
earlier in the search space. 
Therefore, they make your search space 
smaller, and your search more efficient. 
Okay? 
So, in a sense if you think about it, 
this is the computation model of 
constraint programming. 
Right? 
So, you have this domain store, it has 
the domain of the variables. 
And gravitating around if you have all 
the constraints. 
These constraints only talk to the domain 
store. 
They don't talk about each other. 
And because of that, if you handle them 
independently, they don't necessarily 
communicate. 
Right? 
So, they can talk to the same domain, and 
that's what you see. 
Right? 
So this is the first constraint, talking 
to this two domain. 
The second constraints have a domain in 
common, and another one. 
The two constraints have again another 
domain in common and another one. 
And so you see that they are all linked. 
The path can be long, but they are all 
linked. 
But when you reason about them 
independently, you lose that length. 
Okay? 
What the global constraints is saying, 
okay, so let's encapsulate all these 
constraints inside one global 
constraints, which talks to all the these 
domains at the same time and now I can 
actually detect infeasibility. 
Okay? 
So, so now we have done only the first 
thing that a constraint does for a 
living. 
Right? 
Which is testing feasibility. 
The other thing a constraint does for 
living is pruning. 
We want to look at these domains and see 
if we can knock down some of these 
values, okay? 
Because that reduces search space, also 
make the search more effiecient. 
Okay, so the question that we have is 
given a variable a value vi inside the 
domain of variable x i. 
Okay, can I use sin, the value of vi to 
xi and still find the solution to that 
constraint. 
Okay? 
So in a sense what that means is that I'm 
assigning vi to xi but I want to find out 
if that value seems dominant of the other 
variables such that the overall 
constraints is going to be 
satisfied.Okay? 
So how do I do that? 
This is the formula right? 
So I'm assigning xi to the i, okay? 
And then I want to find a value v1 for 
v1. 
Value v, i minus 1. 
Inside, you know? 
For, for the variable xi minus one. 
And so on and so forth, such that this 
constraint is true, okay? 
So I pick up one variable, one value. 
And then I see if I can verify find 
values in the other domain of the 
variable. 
In the domain of the other variable such 
that the constraint is satisfied, okay? 
So look at this, okay? 
So this is once again alldifferent 
constraints. 
Now I have three domains, one two for 
variable x1, one two for variable x2, and 
then one through three for variable x3, 
okay? 
And I'm asking you, can I actually prune 
the search space, okay? 
And the answer is, yes I can, okay? 
Why? 
Well, we know because of this beautiful 
pigeonhole principle, that if I look only 
at x1 and x2, I have two variables, and 
they can only take two value, 1 and 2, 
okay? 
Therefore, if x3, the friendly x3, 
actually take either 1 or 2. 
No, we won't find a solution, okay. 
So what you have to, what you can deduce 
easily, is that x3 cannot be 1 and cannot 
be 2 it has therefore to be 3, okay. 
And therefore, you reuse the search 
space, you know. 
X1 and x2 can take either 1 or 2, 
provided they have a different values, 
okay. 
So the only pruning that you can get is 
remove the, removing the value from 1 and 
2. 
Okay? 
Now, that's the pruning that we can get. 
But once again, if you don't express the 
global constraint, if you use the 
composition here in terms of pair wise 
constraints, you would not prune 
anything. 
Okay? 
Because essentially, for x3, you know, 
when you look at x3. 
X3 and x1, well they can, you know, x, x3 
can take the value 1 and x2 and x1 can 
take the value 2 and that's fine. 
X3 can take the value 1 and x2 can take 
the value 2 and that's fine as well. 
So you never detect that you actually 
have to remove the value one and two from 
x3. 
So the second big benefits of global 
constraints. 
Not only do they detect feasibility 
sooner, but they also actually, make it 
possible to prune the search space more. 
They remove value from the domain of the 
variable. 
And why is that important? 
Because now the domain are smaller 
another constraint can come in and do 
more reasoning and maybe find an 
inconsistency or maybe prune new values 
from the domain which will in, in turn 
probably find some inconsistency or some 
more values from the domain, okay. 
So, this fixed point is very important. 
That's why you remove the search space as 
much you can. 
Okay? 
So the million dollar question though is 
what? 
Can I actually, you know, detect 
feasibility and achieve this optimal 
pruning for this global constraint? 
Okay. 
And the answer to that sometimes we can, 
sometimes we cannot. 
Okay. 
So sometimes we will able, we will be 
able to detect feasibility and I will 
show you examples of that. 
And sometimes you will have to relax your 
standards. 
Okay, which basically means that you 
won't be able to prune everything or you 
won't be able to detect insatisfiability 
all the time. 
but, but you will still get some pruning 
and detect visibility early, okay. 
the other thing that you can say is I'm 
going to sacrifice computation time and 
essentially some of these algorithms and 
one of my students became an expert in 
finding exponential algorithm from 
pruning constraints, okay? 
And what, what you do there is you 
sacrifice time but you will have the 
optimal pruning. 
You will detect infeasibility as soon as 
you can, okay? 
So the answer here is sometimes some 
global constraints you will be able to 
deal with very efficiently, sometimes you 
will have to relax your standards. 
Okay, now I told you when, you know, in 
the advertisement of this class that, you 
know, you will never have to solve a 
sudoku in your life, okay? 
And I'm going to keep that promise, okay? 
And so this is a sudoku and we want to 
solve it using constraint programming. 
Okay? 
So this is a very simple model on how to 
do that. 
Okay? 
So the decision variables are very easy 
right? 
So you look at everyone of these square, 
little square everywhere. 
You know, there will be a decision 
variable associated with that and that 
decision variable will be the number 
which is associated to that square. 
Okay? 
The digit. 
Okay? 
So essentially that's what you see there. 
You know these are the decision variables 
over there. 
Okay, they are basically [UNKNOWN] a 
matrix of, of, of variables, and these 
variables take the value between one and 
nine. 
Okay? 
Now, the constraints of these problems, 
you will have different types of 
constraints. 
The first set of constraints will be the 
fixed position. 
Okay. 
So when you look at this thing, there are 
a bunch of fixed positions all over the 
place. 
We'll have to fix these values, these 
variables to these values. 
And then once again, we have only three 
types of constraints, okay. 
Well, actually one type of constraint but 
three different ways of stating that, 
okay. 
So we have only alldifferent constraints, 
but some of them are going to be on the 
rows, some of them are going to be down 
the column and some of them are going to 
be on the squares, okay. 
So when you look at the first one. 
Essentially that constraint, is basically 
stating, that all the values on a 
particular row have to be different. 
The second one is basically saying that 
all of the values in a column have to be 
different. 
And the third one is basically, you know, 
you look at the square, you know, three 
by three there, and you are expressing 
that all these values have to be 
different. 
These are the constraints of the Sudoku 
and that's all you have to do. 
So this simple program. 
Is why is at least part of the reason why 
I would never do a sudoku in my life, 
right? 
You know it's so simple, right? 
So the next thing that I want to show you 
is actually this is a very efficient way 
of actually solving this thing. 
Okay, so look at this puzzle. 
Okay so the first time I run the program, 
I traced it on this particular example. 
It deduced that, of course it, it fixed 
all these position, and then it deduced 
that this value has to be 2, okay? 
Now, that's very interesting, okay? 
So, I was like how did it do that? 
Okay? 
And so you have to look at a couple of 
things, okay? 
So, you see, you know, there is there is 
a 2 over there. 
Right? 
So, which basically means that I cannot 
put a 2 over here, okay? 
There is no way I can do that. 
Okay, and then you have a two over here, 
which basically means it can't have any 
two on this last line, okay? 
So the tree position where I can actually 
put a two is here and these two gaps, 
right? 
Okay? 
So but look at, look at the, the square 
here in the middle. 
Once again, I know that I have a two and 
therefore, I cannot put a value over 
there, okay? 
Now I also know, what do I know? 
Okay. 
So I know that I have a 2 over here. 
So these guys here, cannot get a value of 
2. 
So the only two positions where I can get 
a 2 here, is these two guys. 
Okay. 
These 2 guys can take a two. 
I don't know which one, right? 
Okay? 
But at least one of them has to take a 2. 
Therefore what I know is this guy, cannot 
have a 2 over here. 
Okay? 
And therefore, the last position at which 
it's get a, get a 2 is over there. 
That's what the system did. 
That's what this pruning for the all 
different constraints were able to do. 
It's magical, right? 
Okay, so if you do that, then it's 
going to know, going to continue deriving 
all these values all over the place. 
That's what it gets, just propagating 
these constraints, okay? 
And then, the system will make a choice. 
It will assign the value 5 at the top 
over there. 
Choop! 
Here. 
And that it will make more deduction than 
when you assign one more value over here, 
okay? 
So there's a value of 4. 
And then propagate and find a solution, 
and that's it. 
Two choice, no back-track, solution 
immediately. 
Okay. 
Now you have to know that sudokus are 
easy for us, and the reason is that they 
have to be easy for human, which 
basically means that human don't like to 
make choices, so these sudoku are 
actually designed so that you can mostly 
deduce the solution and don't go into 
exploring a huge tree. 
That's why these things are really easy 
for constraint programming in general. 
Okay, so, so we have seen now essentially 
global constraints and global constraints 
are these very important area of 
constraint programming. 
There are a lot of people actually 
exploring this. 
Okay? 
And, I want, I want to show you one more 
type of constraint which is the table 
constraint. 
And it's probably the simplest global 
constraint, okay? 
And so this is an example for you to 
understand. 
I have three variables okay? 
x, y, and z, okay? 
This is the domain of the variable 1, 2 
1, 2, and then 3 ,4 ,5 for, for z. 
Okay? 
And then essentially one of the things we 
can think of is, you know, what are the 
possible combination of all these 
variables, okay? 
What are the total possibilities? 
And essentially there are 12 of them, 
okay? 
So you could see each product between, 
you know, the domain of x, the domain of 
y, and the domain of z, okay? 
So that's what we have, okay? 
So in this particular case there are 12 
possibilities. 
So what a table constraints is doing, is 
actually specify a subset of these 
possibilities as the legal, you know, 
assignment of these variables. 
So, in this particular case, we have four 
of them, okay. 
So you see that the first one is 1, 1, 5. 
X is equal to 1, Y is equal to 1, and Z 
is equal to 5. 
The second one is 1, 2, 4. 
That's what you see here, okay. 
And so in this particular case, the legal 
combination is 1 for x, 2 for y, and 4 
for z. 
Okay. 
And so once again what is interesting to 
see is what happens when you get more 
information. 
Okay. 
So assume that I have more information 
about z. 
What's going to happen? 
Well, I know that z cannot be equal to 5. 
What does that mean? 
Okay, so the value z there is not legal 
anymore. 
I have to remove that combination. 
I have to remove all the combinations 
where I have actually z is equal to 5. 
There is only one here, okay? 
And now, essentially, I look at the, I 
look at the other variables, and what do 
I see? 
Look at this guy, look at y. 
The only value which is left in the 
column of y is 2. 
So I can immediately deduce that, in a 
sense, y has to be 2 and the value, you 
know, and this is what this reflect here, 
okay? 
So, so, in a sense, y has to be different 
from y, it can only be 2, okay? 
So that's essentially the table 
constraints. 
Once again, it's a very useful 
constraint. 
It always specify a subset of a cartesian 
product. 
For all the variables. 
Okay? 
So let me conclude this lecture by one 
more thing, okay? 
which is how can we find optimal solution 
in using a constraint programming? 
So remember we discuss graph coloring or 
map coloring actually In the first two 
lectures, okay? 
And so what, what I'm doing here is 
generalizing a little bit of that 
example, okay? 
And instead of using colors, I'm using a 
number from 1 to 4, and what I'm going to 
do now is not only color this country 
such that they get a different color, in 
particular, in this particular case a 
number between 1 and 4. 
But I also want to minimize the number of 
colors that I'm using. 
Okay? 
So basically here, I'm basically saying, 
okay, minimize, okay, what the maximum 
color that this variables can subject to 
the fact that two adjacent countries have 
to be colored differently, okay? 
So, I can do that. 
Okay, so that's a model which is 
essentially optimizing the number of 
colors that I have to use. 
In all the possit-. 
Selecting essentially the solution, the 
feasible solution, which uses the, the 
fewest colors, okay? 
How do I do that? 
In constraint programming, as I told you, 
the focus is on feasibility. 
And what you do when you're trying to 
optimize is you're trying to reduce 
optimization problem to feasibility. 
You essentially solve a sequence of 
feasibility problems. 
You find a solution and then you put an 
additional constraint which says, oh, but 
the next solution is to be better than 
the one that I just found. 
Okay so when we find a solution with four 
color we are going to say I want to find 
a solution which you're only using three 
colors. 
Okay, so we are guaranteed to find an 
optimal solution. 
You know, theoretically. 
You know, in practice it may take too 
long, okay and this is going to be a 
strong method when essentially the 
constraints are too hard, that you add as 
essentially a strong pruning, okay, and 
this happens in a variety of problems in 
results, allocation and scheduling, and 
we'll come to these problems at some 
point in this class. 
Okay. 
Thank you. 
That's it for today.