Okay, this is discrete optimization 
constraint programming part two. 
Okay, so this is the goal of the 
lectures, of the lecture. 
Okay, so we're going to illustrate more 
complex constraint propagation. 
And the underlying topic is the fact that 
every one of the constraints in a 
constraint programming system has a 
dedicated algorithm, okay? 
So that's, so basically, that's the 
technical part, okay? 
So what are we going to do from a non 
technical standpoint, is that, for the 
first time, you're going to see a complex 
propagation algorithm if you have never 
seen any. 
And it's kind of amazing how, how these 
things are working. 
The kind of information that you are 
deducing. 
It's, like, you know, the first time you 
see this, it's like, wow, this program is 
actually pretty bright, okay? 
Of course, it's not, but, anyway, so it's 
going to give you a sense of what a 
constraint propagation algorithm is 
doing. 
It's kind of interesting. 
Okay, so remember, in constraint 
programming is this combination of branch 
and prune. 
Pruning is removing value from the domain 
of the variables in a first 
approximation. 
Branching is, oh, you're stuck. 
There is no propagation. 
You decide whether, you know, you assign 
a value. 
You decide to split the problems into 
sub-problems. 
Typically, you take a values and you 
start giving all kinds of values for it. 
You know, in turn. 
Okay? 
and then obviously, you know, once you 
branch you apply the constraint 
propagation algorithm to prune the search 
space again. 
Now, pruning is basically, as I told you, 
you are using the constraints while, you 
know, removing as many values from the 
domain of as many variables as possible. 
Okay? 
Branching is, you know, in, in our first 
approximation we'll see most 
sophisticated branches came later on, 
later on, but essentially trying 
possible, you know, trying possible 
values for the variables. 
Okay? 
Remember with this beautiful separation 
between the search engine and the, the 
constraint, the constraint store. 
Okay? 
And so what is happening is this guy is 
basically trying to see if the constraint 
is satisfiable. 
And when it, when it tries to derive as 
much information as it can. 
The search will make a choice and send a 
new constraint. 
And the constraint store is to be able to 
say yes or no. 
Okay? 
Am I still feasible, okay, or not? 
Am I infeasible, or am I infeasible, 
okay? 
And if it's feasible, if you believe it's 
feasible, you're going to say yeah, it's 
fine, you know, as far as I can tell I'm 
feasible. 
And sometimes, you know, you add a new 
constraint and then the system will say 
oh, no, no, I'm infeasble. 
You know, remove that choice, give me 
another choice. 
Okay. 
So that's basically the essence of, of 
constraint programming. 
The inside of this constraint store is 
very interesting. 
All right. 
So you have the domain store here, which 
is basically capturing the search space, 
typically associated domains to every one 
of the variables. 
And then gravitating around it are the, 
all these constraints. 
Okay? 
And they don't know about each other, and 
that's the key point. 
Okay? 
And these constraints have two goals in 
life. 
I told you they basically are asking 
themselves, oh, am I feasible with 
respect to this field of, of domains? 
So can I find an assignment for the 
variables using these domains such that, 
you know, I'm, you know, this constraint 
is satisfied? 
And then they will say, oh, but can I 
actually knock down some values in these 
domains, such that I reduce the search 
space, okay. 
And of course, as soon as you do that, 
some of the constraints may become 
infeasible, or some of the constraints 
may be able to knock down more values 
from these domains. 
And that's the constraint propagation 
algorithm, okay. 
Right, the constraint does two things. 
Feasibility checking, you know, is it 
still feasible in the set, we're given 
the set of domains. 
And then pruning, given a set of domains, 
can I knock down some value for the 
domains of the other variables. 
Okay, now the key point, and this is one 
of the topic, one of the topics covered 
today, is that every one of the 
constraints in a constraint programming 
system, has a dedicated algorithm to do, 
these two tasks. 
Okay? 
It's going to test feasibility, using the 
semantics, the structural the 
constraints, and it's going to do pruning 
using the same information. 
Okay. 
So we, so this is the strength of 
constraint programming. 
You can, can explore the structure of 
these constraints to prune the search 
base as best as it can. 
So I'm going to use a very simple 
example, send more money. 
The story here is that, you know, this is 
a graduate student going to going to 
school. 
You know, he needs more money, so his 
father is very, and his mother is very 
reluctant to actually give him money. 
And so every time he asks for money he 
has to find a clever way of asking. 
And so here he's sent, you know, his 
parents a puzzle and that puzzle is, you 
know, if the parents solve the puzzle, 
they will know how much money the 
graduate student wants, okay? 
So that's the story. 
So, essentially the person has, you know, 
three words, send more money, okay, all 
right? 
And the amount of money has to be 
essentially the value of these letters 
over there. 
And you have to make sure, of course, 
that the addition here is valid, okay? 
So in a sense you have to assign 
different digits to all these letters, 
such that addition is valid. 
And then you will have, you know, 
essentially the amount that needs to be 
sent. 
Okay? 
So, now I'm going to show one model, 
okay, for solving this puzzle using 
constraint programming. 
It's not a good model, okay, but it's, 
it's just, you know, a model for 
illustrating constraint propagation. 
So, big disclaimer in many of the, many 
of the examples that I'm going to use, 
the entire, you know, class, is that 
there are many, many models that should 
be better than the ones that I'm 
proposing. 
They are typically chosen to illustrate 
different principles. 
Okay, so this a model like we would do in 
kindergarten, in the sense that I'm 
going to do, you know, column-wise, you 
know, digit-wise addition and use 
carries. 
Okay. 
So when you look at this thing here, 
okay, so you can see that you know, I'm 
going to start with the value d and e and 
summing to y. 
Okay? 
I'm going to get a carry c 1. 
Okay? 
And that carry is basically going to, you 
know, be used for the second, for the 
second column. 
And then, I'm going to generate another 
carry for the subsequent one and so on. 
Okay? 
So, in a sense, the decision variables 
here are going to be of two types. 
They are going to be the letters, okay 
the initial letters of the puzzle, and 
then they're going to be the carries, 
okay? 
And the letters can take the value 
between 0 and 9, they are digits, okay? 
And the carries of course will take the 
value 0 and 1, okay? 
So, that's the basic principle here. 
Okay? 
And so this is one of the models, okay, 
that, that, that you could write. 
I told you this is not the best model 
that you could write, but this is the 
model that will illustrate constraint 
propagation nicely. 
Okay, so what you see at the top over 
there, okay, so these are basically all 
the letters that you have, okay. 
So so, so in this particular case you 
have you know, the letter s, the letter 
e, the letter, you know, n, and so on and 
so forth. 
You have them arranged for the digit 
between 0 and 9. 
And then you have the two sets of these 
different variables. 
Okay, so you see that this is a variable 
value for every one of these letters, 
okay, which have to be digits, okay, 
between 0 and 9. 
Okay, so for every one of these letters 
that you see at the top, you will assign 
a particular digit. 
Okay? 
And then you have the carries. 
There are four of them. 
And the value of them, for the carries is 
0 or 1. 
And then what you see here are the 
constraints for the problems, okay? 
So the first ones are basically telling 
you that all the letters have to be given 
a different digit, okay? 
So this is like you know in the map 
coloring or in the, in the Queens 
problem, okay? 
Basically not equal constraint between 
all the variables. 
Then you see that the value for s and for 
n have to be different from 0. 
These are the most significant digits of 
these two numbers. 
You want them to be different from 0. 
Then you have the value that the carry 
for the last carry has to be equal to m. 
When you actually look at this particular 
equation. 
Okay, so this is the last column. 
And then, and then, essentially you have 
all the other constraints that are 
looking at every one of the column and 
putting and, and expressing the addition. 
And it's always, in general, it's always 
one carry plus, you know, a couple of a 
couple of digits, okay, for, for the 
letters. 
And then on the other side you will have 
one other digit. 
And you will have essentially 10 times 
the carry. 
And that's what you see for every one of 
these constraints. 
So you always see the ten times the carry 
at the end of the equation. 
Okay? 
So that's essentially the model here. 
Okay? 
So it's a set of not equal constraints, 
an equation, and then a set of other 
equations carrying you know the, 
basically, every one of the addition for 
every one of these columns. 
Okay? 
So this is the search space. 
Okay? 
So the search space, initially, what you 
see there are all the digit values, okay, 
and you see all the letters over here. 
You see also the carries there, and these 
carries can take only the values 0 and 1. 
Okay, and once again, you know the key 
point here is that we are going to knock 
down many, many, many values from this 
search page, and that's the goal. 
And in this particular case, there are 
two things that are going to be 
interesting. 
It's how much we prune, okay, using 
these, these constraints. 
And it's also the constraint propagation 
itself. 
We're going to do something with one 
constraint that are going to wake up 
another one which is going to propagate 
again and so on and so forth. 
And that's this kind of propagation which 
is interesting. 
And this is what we are trying to 
illustrate today. 
Okay. 
So, this is essentially the beginning of 
the, of the propagation. 
Okay. 
So you have the not equal constraints. 
These not equal constraints are not doing 
anything initially, because the variables 
have all the possible values. 
And then you have this interesting thing 
here that you know, basically s and m 
cannot be 0. 
Okay? 
And then that m has to be equal to a 
carry. 
Okay? 
So, there are a couple of interesting 
things are going to happen there. 
Okay? 
So, when you see, you know, that m that s 
cannot be 0, you're going to knock down 
the value 0 from s. 
When it, you know, m is not equal to 0, 
you just knock down the value 0 from m. 
And then you have this interesting 
constraint, which is basically saying 
that the carry four is equal to the digit 
assigned to m, okay. 
Now, the carry is 0 and 1, okay. 
At this point, essentially m is 1 to 9, 
so there is only one value which is 
common to these things, and that's and 
that's the value, and that's the value 1. 
So these two guys are going to be 
assigned to 1, okay? 
And that's what you see here. 
Immediately, the system is deducing that. 
Okay? 
And usually once you do that, you know m, 
you know every, every digit, every 
letter, of course has only one value, all 
the other values are ruled out. 
We also know that all the digits have to 
be different, okay? 
So basically these non equal constraints 
are going to propagate and remove the 
value one for all the other, all the 
other letters. 
Okay? 
And that's essentially the state of the 
search space after this you know, a 
couple, you know, this not equal and this 
equality constraint. 
The last equality constraint that you saw 
there, okay? 
So not very interesting you know, right 
now. 
This is mostly what we have seen before. 
So things are going to get more 
interesting when you see this actual 
equation over there, right? 
And so now, we have to find a way to 
actually process that equation, okay? 
So I'm here right. 
And this is the equation on top of me, 
okay? 
So one of the things that we're first 
going to do is to take this equation and 
simplify it given the current state of 
the search space. 
Right? 
So we know that m is the value 1, so when 
we see, you know, the value of m we can 
replace that by the value of 1. 
So the equation becomes a little bit 
simpler, okay? 
And now what we're going to compute is, 
we're going to, to make sure that this 
constraint can be satisfied, we're 
going to compute the value, the, the, the 
set of values at the left of the 
equations and the set of values at the 
right of the equation. 
Okay? 
And obviously, these, you know there has 
to be a non-empty intersection between 
these two things. 
Okay? 
So, we're going to compute the range of, 
of the left, and the range of the right 
of the equation, okay. 
So the range of the left is 3, 11, okay. 
And I want to go slowly and tell you how 
we get that, because this is kind of 
interesting, okay. 
So, we have to, so this is essentially 
how you compute it, okay. 
And every one of these values that you 
see there is computed in a very 
systematic fashion, okay. 
So, look, the 0, which comes here, okay, 
the 0 is from there, comes from the value 
of the carry, of carry of the carry 3. 
So we have two possible values for carry 
3, 0, and 1, okay? 
Now if we try to bounce, you know, to 
have the smallest possible value for this 
left turn, we take the smallest value for 
carry 3 and that's 0. 
And that is the 0 that you see there. 
Okay? 
So the value 2 there is the same thing 
for s. 
Okay? 
So we look at, what is the smallest value 
that s can take and that is what you see 
over there. 
And then usually we get the 1 that is the 
value of m that, you know, that is 
already fixed. 
Okay? 
And so this is the lower bound on the 
value of this expression in the current 
search space. 
Now, we do the same thing for the upper 
bounds. 
And in the upper bound, what you are 
trying to do is to find a maximum value 
for that term. 
Okay? 
So when we see a variable like this carry 
three, we take the largest value, and 
this particle case, it's 1. 
Okay? 
then we do the same thing for, the value 
of s. 
which is, which is nine. 
Okay? 
And that is the value that you see there. 
the value that you see there. 
Okay. 
So that's a value of 9. 
And then we also have the 1 which comes 
from the value of m. 
Okay, and that's how you get 3 to 11, 
okay. 
And we can do that, and we can do that 
for the others, right, which is basically 
giving us 10 to 19. 
I won't go into details, I won't bore you 
into the details, but at this point, 
essentially, I know what is the range of 
the left side. 
I know what is the range the right side. 
Now, to have a solution to these 
constraints, the intersections between 
these left and the range of the left and 
the range of the right side have to be 
non empty. 
And so this is what I'm computing here. 
I'm basically looking at these two 
ranges, and taking the intersection. 
And the intersection has to be, you know, 
10, 10, 10 and 10 to 11, okay? 
So now, I know that this intersection is 
not empty, so at this point, you know, I 
believe that there is a solution, okay. 
So I also know more information. 
I know that this term here has to range 
between 10 and 11. 
If I have a solution. 
And same thing of course, for the other 
term. 
So I'm going to use that information to 
start pruning the search space. 
Okay? 
So what I know is that, if I take the 
left term, okay? 
I know that it has to range between 10 
and 11, okay? 
And now, I'm trying to say, oh, but how 
can I prune the search base using that, 
okay? 
So let's, you know, remove all the mass. 
And now I have just this equation there, 
okay? 
And I see that, you know, 10 has to be 
smaller or equal to the carry 3 plus the 
value of s plus 1. 
And that is to be smaller or equal to 11, 
okay? 
Now, let's assume that I'm trying to 
prune, you know, to prune the value of s. 
What can I do? 
Well I can first you know, take the 1 
which is in the equation and move it on 
the right and the left-hand side. 
And then I have to say, oh, I have to 
remove this carry 3, right? 
So I'm going to push carry 3 on the left 
and a carry 3 on the right as well. 
And so now, the value of s can be bounded 
by these two expressions that you see 
there, right? 
And so what I have to do now, is once 
again, you know, I want to be very 
conservative here, right? 
So I want to see what is the smallest 
value that s can take, okay? 
And I also want to see, but what is the 
largest value that s can take? 
So when I evaluate this expression, I 
have to find a way to find the smallest 
possible value, because if I'm not 
conservative, I can prune solutions that, 
I can prune solutions. 
And the only thing that I want to do is 
prune values which appear in no 
solutions. 
Okay? 
So what I'm going to do here is to look 
and say, okay, the left-hand side, okay, 
has to be made as small as possible. 
How do I do that? 
Well I have a minus you know, carry 3. 
So I have to make this, this carry 3 as 
large as possible, because if it's large 
then I subtract a lot of values, and that 
value becomes very small. 
Okay? 
So how do I make carry 3 as large as 
possible? 
I take the value 1 for that, okay. 
And I take the value 0 to make it as 
small as possible, such that I have the 
largest term on, on, on the right of the 
equations. 
So essentially what I get there is that 
the value of s has to be essentially a 
greater or equal to 8, and smaller or 
equal to 10. 
So this interesting, right? 
So because at this point I can prune the 
search base dramatically for s, right? 
So I remove all these values up to 8 and 
9, okay? 
And this is what this equation has told 
you, and I have only looked at one side 
of this equation, essentially, right? 
So if I look at the other side, okay? 
I know, you know, I have to make sure 
that this side, now, also range between 
10 and 11, okay? 
And so, so I can do exactly the same 
reasoning, okay? 
So I take these two things, I put them 
there. 
And assume that I'm interested here in 
looking I know already that the carry 4 
is equal to 1. 
So I get this expression here. 
Okay? 
And then I can prove the value of, of o 
at this point, okay? 
And basically, it becomes the, you know o 
is to be basically, between 0 and 1. 
And I can, in one step, prune a lot of 
value for o as well. 
Okay? 
So all these values here you know, for 
letter o have been removed. 
At that point, there is only one left, 
which is 0, so I'm going to assign it. 
As soon as I assign it, all the not equal 
constraints, you know linked to that 
variable are going to stop because now 
that variable is only one value. 
That's when this pr, you know, this, 
this, these contraints are propagating. 
Remember last lecture, okay. 
And so, in a sense, all the other values, 
all the other variables there are 
going to propagate there, using these not 
equal constraints, okay. 
So, that's what you see there. 
Okay, so we go back to these constraints 
there, propagate them, and now the search 
space has been reduced. 
And the only variable, the only digit, 
the only letters that can take the value 
0 is o, okay. 
So that's, so what we have done so far is 
propagating all the constraints up to the 
one which is highlighted there. 
Okay, so we propagated the non-equality, 
the very simple equality, the first 
equation, and we are looking at the 
second one now, okay. 
Second one is exactly the same reasoning. 
As I have shown you. 
We are looking at these equations like 
that, and we are going to do the bound 
reasoning that I've shown you. 
Right? 
We simplify it a little bit using the 
value of the variable. 
We know that this guy is between 2 and 
10. 
Okay? 
If this guy is between 2 and 10, we know 
that this guy, to satisfy the 
constraints, has to be between 2 and 10. 
And that's what we are looking at. 
Okay? 
So now we know the value of n. 
Okay, plus 10 times the carry 3 has to be 
between 2 and 10. 
Okay? 
So let's assume that we are interested in 
carry 3. 
If we are interested in carry 3, we have 
to take this value of n and move it on 
the left and the right, okay. 
So that's what we do, okay? 
And this is what we get. 
We get 10 time carry 3 there, okay? 
And then you have the value On the left 
and the value on the right for the lower 
and upper bound, okay? 
Now you look at this 10 times carry 3, so 
once again we have to make this guy as 
small as possible and this guy as large 
as possible to be conservative right? 
Okay, so to make this guy as small as 
possible, what do we do? 
We take the largest value for n, what is 
the largest value for n? 
It's 9, okay? 
So and, the other side, the upper bound, 
we have to make it as large as possible. 
And so, since this value's negated, we 
have to make it as small as possible so 
we will take the value 2. 
Okay? 
So at this point, we simplified the 
equation, okay, which becomes, you know, 
-7 is smaller equal to 10 times carry 3, 
smaller or equal to 8. 
The left side is boring, okay, so the 
right side is more interesting, because 
its fourth is carry 3 to be equal to 
what? 
To be equal to 0. 
Okay? 
So, this guy is not going to be 1, it's 
going to be 0. 
And now, something really interesting 
happens. 
Right? 
So, what we did, what we just did now, is 
looking at this second ineq, the second 
equations, and we found a new value here 
for carry 3. 
Now, the interesting point here is that 
carry 3 is also happening in the first 
equation. 
So, now, we are basically saying oh, but 
that equation has some more information. 
So I will go back and propagate that 
information. 
Okay. 
So remember the fixed point algorithm is 
always looking at this loop, and always 
taking, you know, looking at the 
constraints and until you cannot 
propagate at anything, it's going to look 
at constraints and trying to actually 
propagate them again. 
Now when a value of variable like, oof, I 
show you here, okay, has changed, it's a 
good indication that you should actually 
reconsider that constraint. 
So the constrain propagation algorithm is 
going to take that constraint and try to 
propagate it again and try to obviously 
to find if its still feasible and so on. 
Okay? 
So we're going to go back to that 
constraint. 
So this is the constraint that you see 
there. 
[NOISE] Okay? 
And we're going to simplify it, because 
we have a lot more information at this 
point, right? 
So you see the, the value of carry 4, we 
know, we know the value of o, we know the 
value of n. 
And so, this constraint becomes really 
simple at this point. 
It becomes essentially the value of s is 
equal to 9, okay? 
So once again, what we can do is prune 
the search page, okay? 
And the remove the value 8 from the value 
of s, assign the value 9. 
Of course you are going to propagate all 
the non-equal constraints and remove all 
these values. 
And this is all the search space has 
removed, okay, has been pruned at this 
point, okay. 
So essentially what I have shown you here 
is all these constraints are basically 
you know, influencing every other ones. 
Okay? 
So, constraints are going to propagate. 
Okay? 
Use it's dedicated algorithm to remove 
value from the variables. 
Now, some of these variables appear in 
other constraints. 
These other constraints are going to be 
propagated again. 
Remove more values, which are going to 
propagate other constraints, and so on. 
And this fixed point algorithm is really 
what is the core of constraint 
programming. 
So you basically propagate all these 
constraints until you cannot deduce 
anything. 
And also, you have a dedicated algorithm 
for every one of these constraints. 
Okay? 
So, let me go into the, the, the, the, a 
little bit of the mathematical details to 
actually implement this. 
Which are reasonably simple here. 
Okay? 
So, this is essentially a cons, this is a 
linear inequality that I'm going to show 
you how to propagate optimally. 
Okay? 
So, you see that the left-hand, the 
left-hand side here is basically a sum of 
product. 
Okay? 
A, i, you know, x i. 
X i, a decision variable, a i is 
basically constant. 
So that's the left-hand side, the 
right-hand side is similar. 
The y's are basically decision variables, 
the b's are constant, okay? 
So what I'm interested in, what I'm 
interested in here is essentially 
propagating that constraint optimally. 
Removing as many values as I can, from 
the domain of the variables. 
So I'm going to assume that the domain of 
x i and, and y i are denoted with the 
convention that I used last time. 
So d x i is the domain of x i. 
And d y i, y j is the domain of y j. 
And now what I have to do is propagate 
using that information these constraints, 
okay? 
So the first thing that I have to do is 
to test if it's feasible, okay? 
And the feasibility test here is going to 
be very, very simple, right? 
So how do I make sure that I can, how do 
I test, you know, if this constraint is 
feasible given these domains for these 
variables. 
Well, what I want to do is essentially 
take the left-hand side and make it as 
large, as large as possible, right? 
And take the right-hand side, and making 
it small, as small as possible. 
And if, if by, if the smallest values and 
the largest values don't satisfy the 
constraints, I know that nothing will 
satisfy the constraints, okay? 
So, the feasibility test. 
Look at the left-hand side and replace 
every decision variable by the maximum 
value I can take. 
If look at the right-hand side and look 
at every decision variables, and take the 
smallest value that it can take. 
So that's the min in this domain and then 
I test. 
Now I have no decision variable left, 
only constant. 
And I'm basically test if this is, this, 
this inequality is satisfied or not. 
Okay? 
If it's satisfied, feasible, if it's not, 
it's infeasible. 
Right? 
So, now essentially, I, let's assume that 
it satisfies all. 
Okay? 
Otherwise, I can't prune. 
Right? 
I already pruned the note in a sense. 
And so what I'm going to assume here for 
pruning, is that I have two values left, 
l and r, for left and right. 
Okay? 
Which are basically, the l is basically 
denoting the largest value that the 
left-hand side can take. 
And r is denoting the smallest value that 
r can take. 
Okay? 
So I'm going to use that for the pruning 
algorithm. 
You remember, l is the largest value for 
the, for the left-hand side. 
r is the smallest value for the 
right-hand side. 
Okay? 
So then this is how I prune the search 
space. 
Okay? 
So I want to look at x i. 
Okay? 
So let's, let's look at x x i. 
Okay? 
So what I know is that a i x i has to be 
greater than what? 
So, look at this, look at the, the, the 
initial constraints over there. 
I'm going to look at the right, I'm going 
to look at the right-hand side. 
So the right-hand side is r, okay, so 
that's going to always be there. 
And then, what I have to do is take all 
the other variables here, okay, and move 
it on the other side, so this, they have 
the largest value there. 
And those values are essentially l, 
except that, I don't want to double count 
x i, right? 
So I have to, I have already counted 
inside, I have already counted inside l, 
so I have to remove it. 
I have to remove a i times the domain of 
times the largest value in the domain of 
x of, of the, of x i. 
And that's what I'm doing in this 
expression here, right? 
And so now, I know that, I know that this 
is valid. 
Okay? 
So, I know that a i xi has to be greater 
than that for the constraint to be 
satisfied. 
And that leaves me this pruning rule that 
you have here. 
Okay? 
So, I basically take this expression 
divided by by a i. 
And since I want to be conservative, I 
have to run, well, well, that, that, 
that's fine. 
So, since I'm working with integers I 
have to run up of course, if it's a 
fractional values. 
Okay? 
And this is what you see here. 
Okay? 
So, this is what you see here, sorry. 
so what you see there, is that I'm 
basically taking the seal of that 
expression over here. 
Okay? 
And this is how I prune. 
And of course, y, for y I"m going to do 
exactly the same thing, except that I"m 
going to do, I'm, I'm going to, I'm 
going to subtract the value of y j. 
And then I'm going to divide by, you 
know, b j. 
And then I'll, instead of taking the the, 
the ceil, I'm going to take the floor. 
And I'm going to basically update the 
upper bound of y j. 
So in a sense, so what I do is that I 
update, the lower bound of the axis, I 
update the higher bound, the upper bound 
of the y's, using these two very simple 
rules that can be computed efficiently, 
which essentially, you know, as I told 
you, use the largest value for the x i, 
in the domain of the x i, and the 
smallest value in the domain of the y i. 
Okay? 
So lessons from this lecture. 
First that, you know, you have a 
dedicated algorithm for every one of the 
constraints. 
The constraint propagation algorithm is 
really rich, it's going to propagate 
these constraints until you cannot get 
information. 
And so as soon as you accumulate raw 
information in one variable, it's going 
to propagate to another one, it can come 
back and propagate all these contracts, 
okay. 
And this, and in this particular case, 
the bound propagation algorithm is very 
easy to compute. 
It's basically reason about, you know, 
the, the, the upper bounds and the lower 
bounds on every one of the variables. 
Okay? 
So we're going to see in the next couple 
of lectures, you know, different modeling 
techniques for constraint programming, 
and also different techniques for 
actually pruning the search base. 
Okay? 
See you next time.