0:00

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?

Â 14:17

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.

Â