0:00

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.