Tired of solving Sudokus by hand? This class teaches you how to solve complex search problems with discrete optimization concepts and algorithms, including constraint programming, local search, and mixed-integer programming. Optimization technology is ubiquitous in our society. It schedules planes and their crews, coordinates the production of steel, and organizes the transportation of iron ore from the mines to the ports. Optimization clears the day-ahead and real-time markets to deliver electricity to millions of people. It organizes kidney exchanges and cancer treatments and helps scientists understand the fundamental fabric of life, control complex chemical reactions, and design drugs that may benefit billions of individuals. This class is an introduction to discrete optimization and exposes students to some of the most fundamental concepts and algorithms in the field. It covers constraint programming, local search, and mixed-integer programming from their foundations to their applications for complex practical problems in areas such as scheduling, vehicle routing, supply-chain optimization, and resource allocation.
CP 7 - car sequencing, dual modeling
Loading...
來自 The University of Melbourne 的課程
Discrete Optimization
254 個評分
從本節課中
Constraint Programming
Constraint programming is an optimization technique that emerged from the field of artificial intelligence. It is characterized by two key ideas: To express the optimization problem at a high level to reveal its structure and to use constraints to reduce the search space by removing, from the variable domains, values that cannot appear in solutions. These lectures cover constraint programming in detail, describing the language of constraint programming, its underlying computational paradigm and how it can be applied in practice.
與講師見面
Professor Pascal Van Hentenryck
Dr. Carleton CoffrinAdjunct Lecturer
Computing and Information Systems
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.
