So welcome back. This is Discrete Optimization Constraint Programming, and this is part seven. Okay. So I'm very excited about this lecture, because it's still about redundant constraints. But it's going to be about one of the first beautiful model that I wrote [INAUDIBLE] and I'll will tell you the story later on. Okay. But, we are still in redundant constraints and expressing how you can actually put these new constraints that we put in search space much more. Okay. So, this is actually a real example that I'm going to talk about. It's about car sequencing. Okay. So, what you see there is an assembly line for cars. And you have to understand how this works. So, in practice, you know, when you produce these cars, the object of this assembly line that is moving in front of production unit. Okay. So, these production units are responsible for actually putting options on the car. And an option can be, you know, leather seats or moon roof. But on production, you need to have to go fast, because essentially the, the cars are moving. And so they have a capacity constraint, which is essentially telling, telling, you know, the, the, the people assembling the line, how many options they, how many, on how many cars they can put this option in a row, okay. So, for instance, they may have a constraint that tells you, you know, at most two of the five successive cars you know, can require a moon roof, because otherwise the production unit won't have the time to actually put it on. Okay. So, essentially what you have is a huge amount of cars that you have to produce. Okay. Specifically in the number of hundreds. Okay. And you have these capacity constraints on the production unit. These different cars have different configurations of the various options, and you have to sequence them such that all these capacity constraints are satisfied. So let me show you an example. This is an example of, this is an instance of that problem, okay. So what you saw here on top of the various configurations of car that you need to produce, you know, every time that you see a yellow, that means this is a popular option, which is required. So you can assume that the first option there is a moon roof, the second one is a letter C, then so on and so forth. The tiny numbers that you see there, it's not important what they are, but [INAUDIBLE] basically the number of cars requiring that particular configuration. What you see at the bottom is very interesting, okay. So that's the assembly line, okay. So the capacity that you see there are the capacity of the various production units. The first one there is one out of two. That basically means that every other car cannot require that option. You wouldn't have the time to all, to be, put it on. Okay. The next one is one out of three that means out of three successive cars, well it's actually two out of three. Of the three successive cars at most two can take the option. And the last one is one out of five. Okay. So, if you take five successive slot, at most one car can actually be scheduled there. So, for every one of these constraints, this is actually the legal sequencing, you know, of, of all the cars. If you, you know, if for the first row, if you take, say like, you know two, two two successive slots, only one of them will be yellow. For the last one, if you take any kind of five successive slots, a window of five successive slots, they will be only one car required, requesting that option. Okay. So your goal is to take all these things at the top and produce what is at the bottom, and make sure that every one of these capacity restraints is accurately satisfied. Okay, so how do we do that? This is a simple example that I will use for illustrating some of the propagation and some of the probabilities at the end. So it's good to familiarize yourself a little bit with it, so what you see there are the various classes of car that we have to produce on top of the options. Okay. So this is class one, class one is going to require option one, option three, and option four, okay. And the demand for that particular car is one, so the last one that you see there, this is class six. Okay. It requires option one, option two, and you need to produce two cars of that type. Okay. Now these are the production unit for everyone of the, of the option. Okay, so look at this option here, this is option five this is one over five. Once again window of five slots and only one car of the type. Okay, so that's the example I will use later on. Okay. So this is the model okay, it's a beautiful model. so what you have there is first a set of data. You have the slots that's basically you know, all the slots of the assembly line. You have the various configuration that you see on the top. That's the, the, the type of car that you have to produce. The various options you know, moon, moon roof, you know, leather seats and so on. The demand for every one of these configuration, that's how many cars you have to produce. You have a lower bound and an upper bound for every one of the options, you know. Lower bound means when you have a constraint two out of five, the lower bound would be two, the upper bound would be five. Now, the interesting decision variables here are the line variables so that essentially for every slot of the assembly line, okay. That decision variable will tell you what type of car you have to produce there, okay. Now, we use a set of auxiliary variables here, which are the setup variable and Set up all S when essentially its going to be one when option S is required on slot S of the assembly line. So that basically mean that the sla, the, the car which the, the type of car which is scheduled on slot as S to re, requires [INAUDIBLE] option. Okay. Now we strictly don't need these variables but they make it easy to state the constraints. Okay. So then you see the constraints. The first one is the capacity constraints that you're going to see there. Okay. The demand constraints. And that particular constraints is basically telling you, well if you have a particular type of car, you have to produce enough car of that particular type. Okay. So, and the way you do it is exactly as in the magic series example. Okay so you basically count the number of all currencies of that type, that type of car in the line, and the summation is to be equal to the demand of that type of car. The next constraint is very easy, okay, what it deci, what it basically defines are the set of variables that I talked about before, okay? So set up of OS is going to be equal to the value of requires, which is part of the data, okay. Of all and the, and the type of car which is scheduled in slot S of the assembly line. So in a sense, that's the decision variable. Once we know the value in a sense, we'll know what type of car and then we can compute the set of variables for that part of the car. And then the last constraint is basically the capacity constraints for the production unit. I won't go into the detail, but essentially what you do is you take this time windows, okay, of you know upper bound slot. That's why you see the upper bounds somewhere here. Okay, and then what you want to make sure is that at most, the lower bounds, you know they, they are at most the number of low, the, the value of the lower bound cars that you produce of that type. And that's what these constraints is basically expressing. Okay. So you took the set of variable, you summed them for windows of five and that is to be small or equal to the lower bound. You know two out of five, at most two out of five. You would make sure that this is smaller than two. Okay. So that's the motor. Okay. So it use a lot of the feature of constraint programming. Refine constraints, element constraints, and then the sums over there. Okay, and so this is a little bit of the system is working right. So you see as soon as you place accounts, this is type one, okay. So you know that since the demand is one you will only produce one of these type. And of course there is no other car. That can be scheduled on that slot, okay. Now what is interesting to see is what is happening to the option, okay. So you know that class one over there okay, is requesting option one, three and four, okay. And that's what you see there, right, the blue stuff is basically telling you that the car, you know, that slot is requiring option one, three and four. Okay. And then what you see which is interesting is already the propagation of some of the values, right? So, this is how you get from an element constraints of course, you know we don't require option five. And then you see so the capacity constraint is there. We know that the production, the [INAUDIBLE], the capacity constraints on that production unit is one out of three. So if this car, the first car requires option three we know that the next two, the next two slots cannot require option three, okay. And so this is essentially these two constraints basically acting as soon as you are actually giving a value to a particular variable. This constraint is actually already acting as well, because it made, it removed all the other, it makes sure that none of the other slot can be assigned of a car of type one. Okay. Now, this is more propagation that I'm going to show you. Okay, so you know, this is the demand constraints that I told you about. That's why these values were removed, okay. And then you see this is very interesting what is happening here. Okay. So what you have been deducing here is that, you cannot have a car of class five and six on the second slot, and the reason is because option one. Right? So you see option one over here. Okay. So option one, I know that I cannot take option one. That's what I see over there. I cannot take option one there because of the one out of two constraints. And essentially that tells you, which this is telling you which car are actually requesting option one. And of course you have class, you have class five and six over here, okay? And therefore you can remove these guys from consideration for the slot, for, for the, for the inside the, inside the var, inside the values of the assembly line. Okay, so you made that deduction and you made a similar deduction here for class five, for the third slot over there. Okay, so once again, all this propagation is being done by the system behind the scene. Okay. Now, so with these beautiful examples that I talked about, the first time we run this example, you know, I rem, I still remember it, you know. [UNKNOWN] would work, looking at the screen, and with this beautiful assembly line, and the system would produce these cars [SOUND] almost to the end. And then, just when it was about to reach the solution, it would backtrack and come back. And then it would do that for, you know, half an hour. And were like, why isn't it never finding a solution? Okay. And then we started analyzing, looking at the screen for hours at a time, okay. And what we realized is that the system was actually doing something pretty stupid. Actually the model was pretty stupid. We wrote a bad model and, but we did use a very important feature of these constraints. So, and so this is what we found, found out, okay. So consider an option O and assume that it's capacity is two out of three, and that I have to produce 12 cars, okay. This is my assembly line. I have to produce 12 cars out of every three slots I can produce at most two. Okay, so what do I know? Okay. So I know that, in the last three slots, I can only produce two cars. Okay. So, that I know, and therefore, what do I know? I know also, so I can produce only these two cars on the last two slot. Okay. So what do I know? What do I have to produce in the beginning? Well, I have to produce ten cars in the beginning. So I know that I have at least to produce these ten cars. Because if I don't, I won't find a solution. And that's what the system was doing. It was putting car, no not putting the car, not putting the car. And it was coming here and scrambling around trying to put these cars, but it couldn't, okay. So now, I know that I have to put at least ten cars in this particular pla, in this particular part of the assembly line. Okay. So what else can I deduce? Well, I can do exactly the same reasoning, right? So, I can deduce that I can, at most, put two cars over there. Therefore, I have to produce eight cars over there. And I can continue the reasoning. So I'm deducing a lot of constraints on the assembly line. For every one of these portion of the assembly line. I know how much car I can produce, and I have to produce, okay. Now, is it easy to actually add these constraints? Yes, it's very easy. Essentially, what you are doing here is counting. It's just the same kind of constraints that we did for expressing the capacity constraints. But this time around, what I know is that I'm putting a constraint which is not limiting the number of car by both. I'm actually limiting the number of car by below. And so, what you see here is a constraints where essentially, you know? I'm iteratively looking at larger, and larger portion of the assembly line, okay. actually, smaller on the left, larger on the right. Okay. And for every one of them I'm basically deducing, you know, how much I can produce on the right side, and make sure that the left side is producing enough. So I'm basically taking the lower bond, multiplying by I. I'm taking the upper bond, multiplying by I as well. When I am actually limiting the, the, the search, the, the, the slots that I'm considering. Okay, now that constraint was really powerful. When we actually run the model like this, it would find all the solutions to the benchmark that we had very quickly. And you can see why, right. So this is the assembly line, okay. So I placing the second queen and I'm start deducing information, okay. The second, the second car and I'm placing it there. Okay, so once again I remove value. I'm propagating some of these constraints over there. I know that I need these options. This is two out of five. I remove some values, okay. So I deduce a lot of values like this, okay. And then I can remove some more values using this particular options that you see there, right? So this is, once again, option number four. I know that I can't take, I, I, I, you know, I, I have information of this, I use this particular option to these more values and this is what I do. Okay. And then, essentially, the, the very interesting thing happens here. Okay. So look at this, okay I have to produce two cars of these three classes, okay. And these cars are actually, you know, all using option two, okay. So, in option two I know that I have to produce six cars, okay. Now, look at the assembly line and option two here, okay. What do I know? Well, I know that I can at most, at most put two in here, okay. So, which basically means that. You know, in the first part of the assembly line, I have to put four. Okay. Once again, I play the same three. In these first three slides, slots, I can at most put two, and then essentially, at the rest, I have also to put two. Okay, at most, at least two. This was at most, this is at least. Now look at this tiny thing here, okay. So I have two slots and I have to produce at most two. Well, that's easy, right. I have to put these things over there. Okay. If I put two over there. Okay. This is a two out of three, so I cannot put that one. Now, I have to put two in this thing, and there are only two slots, I put them. And then essentially all the options you know, all the various options for these, all the particular value for these options have been fixed at this time. Now I can start propagating that information to both, and this is what you are seeing here. Okay. So tremendous, tremendous reduction of the search space. Okay. So that constraint, essentially, that what we did was basically doing two things. It was basically looking at the capacity constraints on the line, it was basically looking at the demand constraints. Merging these two to actually derive a new property of the solution, and then essentially what happened is that the search base would be dramatically reduced. Okay. And the system would find solution very, very quickly. Okay. So you see it's continuing. This thing just propagates at this point, on its own. Right? It will never stop. Okay. So what we did here is essentially taking two constraints and merging them for improving the communication between them. Okay. So, so, the various, so let me summarize what we have seen so far. So we have seen various way of improving the communication. One of them is actually introducing global constraints, you merge two constraints. Okay. Another way is actually adding in redundant constraints. That' what you have seen. Then we could add surrogate constraints, that's merging two constraints, you know, for instance taking a linear combination of them. Adding a new one, and then implied constraint is, is just what I've talked to you about now. It's you take two constraints and you derive a property from them. Okay, so that's all the ways we can actually exploit the various, the various the various constraints that you have an combine them, to actually improve the communication. Okay, let me talk about one last thing, which is duel modeling. Which is eh, essentially, pushing this idea, to the extreme. Okay, so sometimes you look at a particular problem, and you have different way of modeling it, and you don't know which one is the best. Okay. So you don't have the same decision variable. You don't express the constraint in the same way. So, what do you do? Well, in constraint programing, one of the nice things you can do is just not borrow. You, essentially, put the two model inside a system. Okay. It's too hard to choose [INAUDIBLE] between them, it's, you know, some constraints are naturally expressed in one and not in the other one. Just put the two models, and connect them in some fashion. Okay. So essentially the basic idea of doing modeling is that if you have several ways of modeling a problem, put them in, link them through constraints, and see what you get. Okay. Because here we exploit the strengths of both models. If you have three, you can put three. Okay. So let me show you a very, very simple example of that. You know, we come back to the queens problem that we're starting from in the first. In the first two lectures from constraint programming. The, you know, I told you that time that there were many modeling of, you know, the eight queens problem, and one of them was to associate a column associate a queen for every column and the decision variable would denote the row. And that's one modeling, okay. And that essentially, the constraint would say, oh, you know, you know, the, the queen's going to be on the same row, upper diagonal or lower diagonal. Here is another modeling. Okay. So instead of us assigning a queen to every column, I assign a queen to every row. Okay. I have a completely different model. Now I'm resigning about the row. And of course, you know, the queens on the row can not be on the same column, and once again you will have diagonal constraints. Okay, let me show you the model. This is the model. Okay. Two sets of variables, no? Okay. You will see the row variables and the column variables. Okay. The row variables are basically for every column it specifies, you know, the row in which the queen is going to be placed. The column variable, okay, so for every row it's going to specify the column in which the queen is placed. Okay. And then you see the constraints here. The constraints are on the two sets of variables, they are exactly the same. You know, kind of, right? Some are on the row, some are on the column, but they're really, really the same. Okay. And then the really important, the really important part is the last constraint that you see is there. And that part is, essentially connecting the two model. So, you have the row model, so far. You have the column model over there. But they are not connected. This makes them connected. So, from what you have learned from the model, is going to be transferred into the other and vice versa. How are they connected? They are connected by these constraints. What are these constraints saying? Take a row, take a column. Okay. So, if we know, that the row of column C is R, it has to be the case the column of R is equal to C. Okay. And of course, vice versa, vice versa, if you know that the column of R is C, it has to be the case that the row of C is R. Okay. So, in a sense, every time I learn something about the row, I'm going to learn something about the column. Okay, and vice versa. Okay. So in a sense, I get not only the propagation of both of these models, but I have information which propagates, you know from one model to the other one. Which can start a new deduction on one of them, and which can start, you know, also the deduction of the other one through these particular constraints. That's it. Thank you.