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.