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.