So welcome back to discrete optimization, this is constraint programming, part
three. And today, what we're going to do is look
at the rich modeling language of constraint programming.
One of the key aspects of constraint programming is the fact that the language
is able to capture very complex model, very complex side constraints,
idiosyncratic constraints. And the purpose of this lecture is to
give you a feel on how you express this model in constraint programming.
So, I'm going to start with a very simple example, you'll see very simple of
examples today, but every one of them is going to illustrate some aspect of, of
the, the richness of the, the language. So this first example is called magic
series. And a series, you know, S zero from SN is
magic, if element I of the series SI represents the number of occurrences of
the value I inside S. Okay?
So, what you see here is the array from zero to four, that's the magic series of
size five. And what we have to do is find these
numbers, okay? Such that the series is magic, okay, so
can you find a magic series? Come on guys, find a magic series.
Okay? So I'll let you think a little bit, okay?
So this one magic series, okay? So you see two, one, two, zero, zero,
why? Well two there for zero so that means
that there are two occurrences of zero. You see one over there, one over there.
One occurrences of one. This is itself, right?
So this is a little bit self referential. And then you have a two there, which
basically tells you that there are two occurrences of two, this one and that
one, okay. And, of course, there are zero
occurrences of three, zero occurrences of four, okay?
So now what we have to do is to write a program that will find magic series up to
a thousand or something like that. The length of the series would be a
thousand, okay, and you can do this, okay?
So this is a simple model, okay, for doing this.
Okay? So, what we have there is essentially the
size of the series, then you have a range, and here you have the decision
variables, okay? So the decision variables you have one
decision variable for every element in the series.
And it denotes the occurrences of that particular element inside a series, okay?
What you see over here are the constraints, and that's the most, most
interesting part, okay? For every value, okay, from zero to the
life of the series okay, so you have one of these constraints.
And that constraint specify the number of occurrences of K inside a series, okay?
And how do you do that? Well you have this expression here, which
is basically summing for all I inside the series, okay, and what are we summing?
We are summing this, you know, this constraints essentially, this condition
which basically tests if element I of the series is equal to K.
Okay? So, one way to think about this in a
sense. This, this, this is the key in this
example, so one way to think about this is assume that every one of the
decision's variables, have already been given a value.
What you're doing here is testing if this condition is true or false.
Okay? If it's true, it has a value one.
If it's false, it has the value zero. So what you are really doing here is
summing all the constraints and finding out if they are true or false.
And if they are true, you get a one, if they are false, you have zero.
And that's essentially equivalent to summing the number occurrences, of key
inside a series, okay? So what you see here is a, what is called
a reified constraint, it's a very, very useful uh,con, concept.
And it's basically the ability to transform a constraint into a 01 value,
okay, a 01 variable, okay? And so as I said before, the variable is
going to get the value one, if the constraint is true, it's going to get the
value zero otherwise. Okay, let me, let me explain a little how
this whole thing works. Okay so this is essentially taking the
model and unfolding it, okay so that you see every part of the sum okay?
So you see the series zero is what, it's the sum of series zero is equal to zero
plus, series one is equal to zero, and so on and so forth.
Okay, so you are testing, you know, how many of these variables have the value
zero. Okay, for series one it's exactly the
same thing, but now you're testing if the series one, if series zero is equal to
one, if series one is equal to one, if series two is equal to one and so on.
Okay? And so you basically have this big system
here of constraints. Every one of these sub-constraints here,
every one of these constraints is, consists of many, many sub-constraints
that you see over there. Okay?
So, now you have to find this series, of course.
And one of the things that we can do is start giving value, okay?
So if you give the value one to to, to series zero, what is happening?
Well, essentially you put a one over here, okay?
So that's the value that you have, okay? And no of course, you know, by
definitions is, if series, you know, zero is equal to one, you know that there is
at least one occurrences of one, and that's what you see over there, okay?
So we took the test over there, it's true now, you have this one over there.
And of course, all the other values there, you know they are false and
therefore you replace them by zero, okay? And so this is the new system now, once
you have this additional piece of information.
You simplify it the whole system of constraints.
Every time the constraint becomes true you replace it by one, every time the
constraint becomes false you replace it by zero, okay?
And so now for instance at this point, you know that series one is greater than
zero, and therefore you can look at, you know, you can look at that value and know
that as series one is equal to zero you can remove it.
And once again, you simplify the overall system.
That's what's going on behind the scene, that's how the propagation works on reifi
constraint, okay? So, what is happening behind the scene?
This is what the system does when it has assistance, including reifi constraints.
Essentially what it does, it replace every one of these expression by the
booleq variables, okay? So if we have these Booleq variables that
you see over there. And then you state constraints and these
constraints are basically turnary constraints instead of binary constraints
now, okay? So you have a constraint which is called
booleq, okay? Which now takes three variables, okay?
The Booleq variable that we just introduced.
And then s i and k. And basically a constraints like this,
this is a specification of the constraints, right, so bool B, X, V,
okay? And that constraints is going to be true
if B equal one and then X is to be equal to V, or if B equals zero, then X is to
be different from V. So in essential what we did all, all, all
of these reifi constraints, and replaced these by these turnery and their new
booleq values. And when we do the sum, this is piece of
cake, right? So the only thing that we are using here,
are basically the booleq variables, okay? So in a sense, the beautiful model that
I've shown you is basically automatically compiled by the system into a system like
this. Into this model, which essentially
doesn't reason about reifi constraints anymore.
It reasons about natural, you know, simple constraints between booleq
variables and other variables. Okay?
Now, let me move to another example which is called the Stable Marriage problem.
Okay? So, now, here I'm not going to define
what is, I'm not going to argue what a marriage is.
This is a scientific problem, here. Okay?
And for the purpose of these examples, which have been defined a long time ago.
Okay, the marriage is going to be between man and woman, okay?
And so what we are interested in doing is essentially marrying this couple of
beautiful people. You can see how beautiful they are right.
And we have to marry them such that the marriage are going to be stable.
You know once again we have a bunch of men and we have a bunch of woman, okay,
and we have to marry them together. The input, the only inputs that we get.
Is that for every woman is going to provide a ranking for the man okay?
So that's what you see there and of course every man is going to do the same
for every woman, okay? So you see there Hugh is basically
ranking Angeline on top, and then you know Holly and the Kara, and then Julia.
Okay, and then on the other direction you know Holly likes, you know Clive very
much, and so on and so forth. Okay?
So for every woman your going to get a ranking of the man, for every man your
going to get a ranking for the woman. And now we have to make sure that these
marriages are going to be stable. Okay?
Now, we have absolutely no clue how to make people fall in love.
We even have less clue to make sure that they stay in love.
But we going to do a scientific approach to this problem, okay?
And this is the key, okay? So these are called the stability rules
for a marriage, okay? So, and we going to say that a marriage
between Hugh and Angelina is stable. If two conditions are true.
The first one, if Angelina prefer another man, let's say George, right.
So just taking you know, completely randomly George, okay?
So if Angelina prefer George over Hugh, then George must prefer her spouse his
spouse, over Angelina. Okay?
So Angelina wants to switch to George, but George say no, no, no, no I'm fine.
You know? And so, of course you have to have the
opposite rule right, so if you prefer another woman, let's say Julia over
Angelina. Then Julia must prefer her spouse to,
over Hugh. Okay?
So in a sense what Hugh have is that you know, Hugh and Angelina may not be very
happy, they both want to switch but they can't.
They are stuck together. Okay?
So that's why the marriage is stable. Okay?
So that's what we want to do. We want to write a motor here, such that
we design a set of stable marriage for all these Hollywood stars.
Right? So what are the decision variables?
Well there would be two sets of decision variables.
There will be for every man we'll find a wife, and for every woman we'll find a
husband. Okay, so that's going to the decision
variable. And that's what you see at the bottom
here. Right?
So for every man you find a wife, which has to be of course, a woman in this
particular case. And then for every woman, we have to find
a husband, which is in this particular case a man.
Okay? You have the data here.
Okay? So you see all the men, all the women,
you have also the preferences for the men and the women.
Okay? So wrank of Hugh, Julia means what is the
ranking of Julia in the ordering of Hugh? And the lower the value, the higher the
preference. For that particular woman, okay?
And, of course, vice versa for the men. Okay, so this is basically telling what
is the ranking of Hugh inside for, for Julia.
Okay? So, the first thing we have to do, and
this actually very, very nice, is we have first to specify the rules of marriage is
this particularly example, okay? And the way we'll do that is simply by
specifying that you know, if I'm married to someone, that someone is to be married
with me, and this is what these two rules here are basically saying.
For every man, the husband of the wife of that man is to be the man itself, okay?
And, you know, equivalently for the woman, okay?
So the wife of the husband of a woman has to be the woman herself, okay?
So that's the first set of rule that we have to, to express.
And there is something really, really interesting about these, these
constraints, right. So what you see here is that, you know,
wife of m is a decision variable. That's a variable, and it's indexing
husband, which is also an array of variables.
So you have a central variable, indexing an array of variables.
Okay, very expressive feature, of, you know, constraint programming languages.
Okay, now the next thing an the last thing we need to do, is to actually
state, all the stability rules of the marriage.
An that's what you see in the last four lines here.
Okay, so we going to take every man an every woman, an then every woman an every
man, and we go to state of the marriage has to be stable.
Okay, so what, oops, what you see here, is, is the first, the first stability
rule. Okay?
And what this means is that m prefers w over his wife.
Okay, so that's the left part of this condition.
Okay, left part of this condition of this simplication here Is the fact that m
prefers w over his wife. Now, if this the case, what we have to
make sure of, okay, is that you know, the woman prefers her husband over m, okay?
And that's what the condition that you see here is expressing okay?
So essentially what we have here is a condition which say, is saying that if a
particular man prefer a particular woman over his spouse, then it must be the case
that her woman prefers her husband over this man, okay?
And so once again what is interesting here is two things, first it is a logical
implication, okay? Nice, we can express all kinds of logical
constraints in this language. The other thing that you see here which
is very interesting. And once again, what we have here is a
two dimensional matrix of preferences, okay?
Matrix, you know, it's a matrix event in this particular case.
But we index it here, okay? As you can see, by a decision variable,
okay? So once again, a big array, big matrix
index by a decision variable. Okay?
So that's all we need, that's the entire model, and with that we can solve all
Hollywood's problems. Okay?
there are two interesting features I told you.
The first one is called the element constraint, it's the ability to index a
rate or a matrix with complex expressions involving variables, all single
variables. And then we have the ability to activate
increment logical combination of constraint.
Okay? So, that's to address what I said to you.
Okay? So, let me, let me go into a little bit
of the details of these features because they are interesting.
And what you want to understand is how actually they are used in pruning the
search space. Okay?
So, we're going to look at the basic, the simplest element constraints.
Right? So, you have X and Y which are variables.
Okay? And we have an array C.
Okay? That array C is an array of Constantin's.
Okay? It could be an array of variables in the
most complex case. In this particular case, we adjust an
array of int, okay? And then the constraint is [UNKNOWN],
okay? So we are basically saying that C is
equal to CY, okay? So once again, you know, this c here,
that you see, okay, that's an array of int, okay and Y is a decision variable,
okay, X is a decision variable as well. Okay?
Now this is an example. Okay?
So I'm going to, I'm going to show you the various example.
You see X over there and the value that it can take, the, the X over there it can
take the value between three and five. And you see Y there, which can take
between zero and five. Okay?
So that's the domain of these variables when we start, okay?
So we, I, I'm going to assume that we have that, okay?
Then you see the array C, okay? So this is the array, array at index
zero, it has the value three. At index one, the value four, and so on
and so forth. And at the last index five, it has the
value three, okay? So that's what you see over there.
Okay, now what is this constraint doing, okay?
If I have the information that X is to be equal to X is not three, what's going to
happen? Of course the first thing we can do is
remove that value from the domain of the variable, okay, that's what you see over
there. Okay?
But can you deduce something more? Okay?
So what we know is that what, what the constraints is going to do is look, you
know, the constraints is x=c[y]. So we want to prevent Y from taking a
value that's going to give three to X. Okay?
How do we do that? Well we look at the value inside of the
index which has a three. Okay?
There is the first one the index zero, and there is the last one which is index
five. Okay?
So we can, we have to actually remove the value zero and the value five from the
domain of one. And that's what you see there, okay?
So we remove the value zero, we remove the value five from the domain of Y.
So in a sense what is interesting here is that if I know some more information
about X, I can propagate it directly on y.
Okay? So, no, assume that I've learned
something about Y. I've learned, for instance, that Y cannot
be four. Okay, what's going to happen?
Well, Y cannot be four, so what does it mean?
It means that Y here, you know, I cannot index this array with that particular
value. And that particular value is four, okay?
So it basically means I removed it, okay? But nothing happens to this one, okay?
Because the value four can also be of time if, you know, Y is taking the value
one which is over there, okay? So, at this point I cannot remove anybody
from X, okay? So this is essentially only removing some
part of these array, but you know, I can still assign the value four to X.
But if, if Y now is different from one, then I can remove this value one over
there, okay? Please.
Yes. And then essentially at that point, you
can see that the only value which is left for X is the value five, and therefore X
has to be equal to five which is what you saw, oops.
What you saw just before, okay? So I'm running over the animation again
to tell you that the end game here has only value which is left for X, which is
five. And only two value which are left for Y
which are two and three. Okay?
So that's the element constraints. Two thing which are interesting,
propagation goes from Y to X, and from X to Y.