this could optimization local search, part two.
more concept and the main concept today is going to be the concept of swaps.
But there will be another set of really interesting concepts on the way you'll
see that. So let me start again with the car
sequencing example. You'll remember these beautiful cars,
right? So basically what we have is an assembly
line we have to produce these cars from this assembly line but these cars are
requiring different types of options right so leather seats, moon roofs all
these kind of things. So when you produce this car as we saw
previously you have to basically sequence them on the assemnly line in such a way
that the production unit Have the time to put the options on the cars.
Okay? So how, how do you do that is really the
question here. Okay, that's what we have to solve.
We have to sequence these cars such that production unit will have the time to put
the options on the car. Okay?
So this is a configuration. This is a solution acitvity that we saw
before. You know every one of the roads you see
over here okay so that's the capacity constraints.
That about the eruption lets say [UNKNOWN] and the capacity of that one is
one out of two which basically means if you take two successive slots you can at
most one one cause requiring interruptions otherwise the production
won't have the time to actually put the options on the table on the On the, on
the car. So so when we look at this thing from a,
from a local search standpoint, what are we looking at?
While we, what we'll do is we start with a sequence, right?
We always seq start with, with configurations and that configuration may
be completely violating these capacity constraints, okay?
That's the way local search works. And what we're going to do here is, we're
going to look at that configuration and we're going to look at 2, 2, 2 parts of
the assembly line and we're going to swap them, okay so that's the basic idea here.
Okay? So we're going to take two
configurations, you know 2 types of [UNKNOWN] and we are going to swap that.
Swap that. Okay?
So, the first strategy therefore, is going to find a car configuration.
Okay? Which appear in some violations, that
means that some of the capacity constraints or maybe several will be,
will be violated and what we will do is to swap that particular type of car with
another car in the assembly line. Okay?
And the goal of course, is going to be trying to minimize the violation.
Okay? So, every one of these moves.
Its goal will be mining, minimizing the overall violation of the capacity
constraints. Okay?
So let me illustrate that on an example, okay.
So what you see here are all the, all of the assembly line that, the exact way we
saw it for constraint programming. The, the diagram on the bottom, there, is
essentially looking at all the options, and that's How we will be able to look at
the violations. Now, the table that you see here, okay,
is basically the various configurations that we have produced.
I won't talk about it very much, because you'll see everything here.
Here. So the beauty of local search is that at
every point you see the everything because you've assigned you know
essentially all the, all the, all the decision variables.
Okay so what you see here is that we produce the various types of car you
know, we had a demand for 1 for this one, 1 for that one, 2 for the you know to
that 3rd type of car and so on. And so essentially what you see there is
basically a completely arbitrary configurations at the beginning, Okay?
Now we look at the options of that car and that's the kind of options that they
require, okay? So you see for instance that here, you
know, we have three cars requirirng option one, okay and we know that the
capavity is one out of two so they will be violations there.
Okay, and you see all the other options being required by the various types of
cards. Okay so now we have to find we have to
understand the concept of iteration right.
So these capacity constraints are huge stuff right so they look at the entire
line. But there is a very, very nice way of
actually capturing the violation. What you do, is that we know the capacity
of this guy is one out of two. So what we are going to do what you see
there, right. We are going to take this window, this
sliding window of two slot of a time, okay.
And then we are going to look if inside that window, there is a violation or not,
okay. So in this part of the case, we see a
nice, you know. Two slot window.
Only one carries, requiring the option so we're know that we are fine.
Okay? So for the next for the next option, just
a little bit complicated. Here my hand is probably not big enough
but we have a window of three slots. And we are looking if there are more than
two cars actually requesting that option, OK?
So we can do that for essentially all the various options there, really big at the
end because they're windows of size five. So in a sense, what we can do is we can
take these windows and move them along the slot, the assembly line essentially
And so you see this nice you know, window which is moving and at every step, okay,
what we are doing there is looking how many cars are requesting that option in
that particular window, and if there are more than one is this particular case we
will have a violation. So essentially the violations are
going to come when you are in a particular window okay?
We are, the window is in a particular part of the assembly line such that the
capacity of the production unit is violated, okay?
So in this particular case what you see here is that it's violated so we know
that we have one violation. We move it a little bit.
to the right and we see another violation and then the last slot of the, the last
two slot of the assembly lines have also two cars there requesting that option so
we know that we have another violation. So, in this particular case, we know that
the first, the capacity constraints of the the first option is violated three
times, okay? Now, we can do that in a very similar
fashion for the second option, okay? So also, you know, show which cars are
here. Which, which options are basically
violating the capacity constraints. We could do it for the next one, and we
see that in this particular case we have two, we left two violations.
Okay? And that's what you see there.
And we also see which essentially slots are violating that particular
constraints. Okay?
And we can do that for every one of the lines.
And you see. You know in this particular example, how
many of the, the, the capacity constraints and, and how much the
capacity constraints are violated. Okay.
So the, the, look and such, no It's basically going to take configurations
here, okay, types of cars, which are appearing in some violation, and then
swap them together. Okay, so we take one, we take another one
we swap them together we observe the two costs and obviously we have to [UNKNOWN]
all of the violation and which of the slots inside the assembly lines Are
basically in valuations. Okay, so we did, we did one move.
This is another move. We take the, we take care two and car 10
and sub them together. And we reduce the valuations again, so
there is at least at this point, there is only one tiny violation.
And we could continue doing things like this, and in this particular case we keep
one violation and we can continue. These are the various local moves that
you can do, okay? So, the key point here, is that compared
to the queens example, what we are really doing Is swapping cars.
We are not assigning a value to a particular to a particular to a
particular to a partiuclar slot. So why do we do that?
Think about it. Why are we essentiallyy considering
swaps, and not assignments of values to the decision variables?
Okay can you think about it? So the reason we are doing that is that
we are automatically by doing that maintaining the satisfaction of one type
of constraints, the demand constraints. So we are making sure that at any point
the demand constraints is always satisfied.
We always produce The right amount of cap So that constraint, we can just forget
about it. Okay?
So because we at all the first, the first, you know the first configurations
that we had at all the cars that we needed to produce, once we swap, we keep
exactly the same number of constraints, and the demand constraints is going to be
satisfied forever. Right?
So this is the key aspect here. So, in a sense, you know if you tried to
abstract this a little bit, what we have is two types of constraints.
There are the hard constraints, they're the constraints that you want [INAUDIBLE]
of search procedure to satisfy all the time, and then you have the soft
constraints, which are very nice because you can violate them and try to violate
them less and less. Okay?
So the key idea here is that in many of these complex problems, what you do is
you separate the two constraints into the hard constraints and the soft
constraints. You maintain the hard constraints.
They are always satisfied by the local search and then the soft constraints can
be violated and used trying to decrease the number of violations of these soft
constraints. That's the basic power line here, when
you try to solve satisfaction problems, okay?
So let me move to another problem that we saw.
And discuss how we can actually solve it wit local search again.
This is a magic square where we trying to have this a square and trying to pit all
different numbers into the various square such that the sum of the diagonals, the
sum of the horizontal line, the rows and the and the columns.
Were equal to the same number. So this other constraint that you saw
okay, and essentially they constrainting that all the, the rows and the column,
have to sum to t, and then you have the sum of diagonals, and once again you have
to sum to t, and then you have the all different constraints, which is basically
specifying that every one of the squares in the big square have to have received a
different number. Okay?
So, once again, we're going to do exactly the same thing.
We're going to split these constraints into two sects.
A hard constraint and then a bunch of soft constraints.
So, the hard constraints here is going to be the all different constraints.
Now, I'm going to make sure that we only assign different numbers to every one of
the squares. Okay, the slot in the squares, in the
square. And the other constraints, essentially
here the inequalities, the equalities for the rows, the column, and the diagonals,
are going to be soft constraints. We can violate them, and we'll move
towards decreasing these violations. Okay.
So, you know this is a particular configuration that we have.
Look all the numbers here are different. Okay?
And what we are trying to do is making sure that the you know, the rows, the
rows, the columns and the diagonals sum to the same value.
Okay? Now, the real magic number that we want
to find here is 15. Okay?
But we see that this particular column here sums to 17.
[SOUND] You know, violation. Okay, that constraint is violating.
This one is summing to 14, it's also violating, we have another violation.
This constraint is also violating. I mean the whole thing here is violating.
We are in a completely you know terrible state so we are not satisfying any of
these constraints. OK?
So, since we have these hard constraints, you know which is keeping all of these
numbers different. OK?
What we're going to do is, basically, look at, again, at the swapped neighbor
root. We're going to take 2 positions in the
square and going to swap the values. And we're going to look at the effect on
the violation. So, now if we swap 8 and 3, what's going
to happen? Is that, you know, the sum of the rows
and the columns and so on? And the diagonals are going to change?
But in this particular case all the constraints are violated again, okay.
Now, when you look at this you say, this is a nice neighborhood, this is a nice
way of modelling the problem. But every time I swap, you know, most of
these constraints are going to still be violated.
And therefore I get essentially no information, right.
So in a sense I have nothing, nothing at all to drive my search, OK?
So that's where essentially you can think of another way of representing violation.
Instead of you know having this kind of mannequin approach, its I have violated
or not. OK?
So what you can do is to look at how much These constrains are violating.
Is, is this constraint violating a lot, or not?
Am I getting closer to the right value, or not?
Okay, so that's what we're going to do. Because if we only look at the zero and
one values, essentially We don't have enough information to actually drive this
search, okay? So what is, what is, what is, you know
what is the amout of violations of an equality?
Well, if you look at the value of the left hand side, you look at the value of
the right hand side, you take the difference between them and the absolute
value, okay? So once you do that, you get a sense of
how much that constraints it's violating. An therefore, you know, when you make a
local move you can see that the violations of these constraints are
actually decreasing. Instead of saying yes or no, you have
something that tells you, yeah, yeah, yeah, yeah, yeah, you are making
progress. An that's what we are going to use, okay.
So once again, you know, the magic number that we want to get is 15.
You see all the numbers here, you know for all the variations.
But now the goal is not to find out you know, is this [UNKNOWN] satisfy enough.
Is the, the basic idea is that can I get closer to 15 for everyone one of these
rules verbally? Okay, so you see that here, you know, for
that particular value, 17, the distance with respect to 15 is 2, so I have, you
know, the degree of violation here is 2. Okay, so you look at the next one, 14,
the distance to 15 is 1, so you have one violation.
So when you look at everything here, you know, you see, essentially, the various
violations. Of the various constraints.
And you have a much finer measure on the hole close this configuration is a part
of a feasible solution, OK? So the number of violations here while
they're not to the degree, the order of the degree of violation is 21, when you
swap these two guys know what happens, OK?
So you can see that You have decreased the overall number of violations.
It's 14 at this point. Okay?
So in a sense, and this constraint is satisfied, okay, so there is zero degree
of violation. But, overall you can see also that the
various degree of violation of all the constraints.
You know you see how these degrees are basically evolving.
And so your goal now is to not minimize the number of violations but minimize.
The overall degree of violation of the entire system.
So different, but giving you more information.
Okay. So we keep swapping, we swap 7 and 4
here, and we decrease the total number, the total degree of violation to 5, so we
get closer, closer. Okay, so we keep, you know, solving 8 and
7, and then magically, okay, wow, that's a good name for this problem, right,
magically, we solve the magic square problem.
Okay, no violation anywhere. And we have a solutions.
Okay, so the two key ideas that you see here is, once again, okay, so we look at
this problem and we identify some hard constraints and some soft constraints.
Okay, the hard constraints here is that all the digits Have to be different, and
we maintain that. By swapping them, we don't change the
number of digits or the nature of these digits, okay.
So that's how we do a swap neighborhood. We maintain automatically one of the
constraints, it's always going to be feasable.
And then a second idea here, which was improtant, is that we sometimes don't
want just to resolve about whether a constraint is violated or not.
We want to find out how much is violated, and that's what we use for actually
solving this problem. Okay?
So, we'll see you next time. And talking about optimization.
Look and search for pure optimization products.
Thank you.