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.

Â