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.

Â