1:39

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.