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.