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.