Good morning. Okay, back to discrete optimization local search. And so, so far ,one of the things that we have done is looking at all these neighborhoods and you know, we saw a variety of them. You know, some from very simple to very complicated one. What we want to do today is step back a little and actually look at how we search these neighborhoods. Okay? So we have talked about the neighborhood but not really how we use them. For searching. It was very implicit. So what do we want to do in the next three lecture, is take a systematic look at how we can exploit these neighborhoods and do local search on top of that. Okay? So more systematic presentation, and then we going to, you know, study heuristics and metaheuristics, okay? And so, that's going to be a focus of essentially the lecture today and the next two lectures. So today mostly are heuristics, the next two lectures, metaheuristics. Okay? So remember local search work with states, okay. At any point, we are in a state inside a resolution, if we only explore you know, feasible configuration. Or it's a configuration where there may be violations, some of the constraints are violated. Okay? Now, essentially, the local search is going to move from the, from state to state, okay? And essentially, from one state, you can only move to a subset of states, which are called the neighborhood, okay, of that particular state. So, we're going to use the function N(s) to denote the neighborhood of state s. That's all the other states that you can reach when you are at s, okay? Then we're going to introduce this legal function, which basically tells you, you know, that from all these neighbors that you can go, which ones are legal and which ones are not. Okay? So there would be the subset of the states that you can move to. Otherwise, you will be basically preventing the search from going there, okay? So this is, this is kind of a being implicit to what we have done before, okay? So always moving to something which is a better place. Okay, but we'll many other ways to do that in this next three lectures. Okay, and then once we know which neighbors are legal, what we are going to do is select one of them. And once again there will be many many ways of actually selecting the neighbors. Okay, so what you get is this crazy function, you know, S of L of N of s and then are all the other S's that you can use in the other function. But essentially, what you do, you select a legal neighbor, okay, from the state you are in. Okay? So, the algorithm, and of course, what we want to do is of, is of use in some cases is minimizing an objective function. Almost always, either it's minimizing violation or it's actually optimizing an objective function from the problem specification. Okay? So, this is the general pattern that we're going to use in the next couple of lectures. Okay? So, you have the local search. You know you have the objective function f. You have the neighborhood N and so we'll give you a definition of that. We'll pass that to, to the local search. You have the function L and the function S, for which neighbors are legal and then what is the selection function. Okay. And most of the local search, you know we'll adapt this a little bit from time to time. But most of the local search, I'm going to start from a configuration that you generate and you can have different ways of doing that. And of course, that's the best solution you have at that point particular point. So, S star is like, keeping the best solutions at this point of the search. And then you're going to do a number of iteration, every one of them is going to go to a neighbor and so and so forth, okay? And obviously if the neighbor sees satisfiable and he has improved the current best solution you will, and you have found a better solution, we have found a better solution and we store it. And otherwise, what we do, we move to the next neighbor, and how do we do that? Well, basically, we select a legal neighbor in the neighborhood of s, okay. So and at the end of the search we returned a best solution we had found, okay. So this is schema that we going to use. And one of the goals today is give you some example of what L can be or what S can be or what you know and most, mostly we'd seen what the neighborhood can be. Okay, and so that's the goal. The goal is to look at these L and S function and so all the variety of things we could do there. Okay. So this is an illustration. Graphical illustration of what we do. So we start at a particular state. Oooo over there. Okay. and then essentially what we're going to do is define the neighbor of that station. This is the regions that you see here. That's all the neighbor. Eventually we can move to all of them. But then we put these restriction. Okay? So I only want to look at these neighbors which satisfy this legal condition. And now you see all these three neighbors there in this particular case. And then we select one of them. This is you know, the selected neighbor. Okay? And then we move. Okay? And so now we have moved from you know, the original note to the selected note. Okay? We restart the process. These are all the neighbors. Okay? Some of them are legal, some of them are not. Okay? And the, you select one of them, okay? So, you know, here and then you move to that place and you continue doing that and you see the search moving [SOUND] all over the place until it reaches the final state. Isn't that beautiful? We have to do it again, I mean, it's so beautiful, you can't imagine how much time we spent doing this so I want to show it again. So we start from this, we selct the neighbor, okay, the legal ones, we move, okay? We do the same thing, we selEct the neighbor, the legal ones, we move. Okay? And then we keep moving, okay? And so this is essentially, what we going to do today. Okay. Looking at, not the neighborhood, because we have already seen many of those things. But looking at what this legal function is, and how we select a particle and neighbor. Okay? And there are many, many ways to do this. People are really creative in this feat. Okay? So, for instance, one of the things we have seen so far, many, many times is only looking at local improvements. When you are in a state you only want to move to another state and in this particular case which is better than the current case. Okay, so you always want to improve. Okay. In a sense, you always want to go up, up, up, up. Okay. Better and better. Actually we are minimizing so down, down, down, down. Okay, so and the selection function many times what we have done. Is looking at something which is greedy. You look at all the neighbors that are improving, and you take the best one. Because somehow, you know, you believe that this is going to give you the best solution quickly, okay? So these two things are things that we have seen, you know, kind of implicitly so far. Okay, now in this field okay, in the, the local search we typically distinguish between heuristic and what is called meta-heuristic. Okay, so one of the things in, in optimization that you have seen so far right, is that we are always very good at choosing nice names. Like heuristic, metaheuristic, and you see many of very fancy name today, okay? So we are very creative people, okay? A heuristic is something that, essentially, tells you how to choose the next neighbor, okay? It's basically telling you, okay, this is the heuristic, this is the way you want to choose the next neighbor to go to, okay? And typically, you use only local information, the state s at which you, you are and then the neighborhood obviously. Okay and the goal of this heuristic is essentially to drive you down to a local minimum. Okay? To a local minimum, a good one hopefully. Okay? Now, the metaheuristic is a little bit different. Okay? So, the goal there is going to be escaping local minima, okay. So, so if you only do local searches let's say using greedy improvement, you're going to get to a local minimum. Most of the time you have no guarantee on the quality of it. Okay? So, the metaheuristic is going to say ooh, you know, I'm stuck here but, I want to try to get out of there and see if there are other local minima that are good. Okay? So, that's what you're going to do. Okay? So, essentially what you want to do is use the metaheuristic and we see a bunch of them. Right? We will see how they can derive the such all of local minima and trying to get closer to the global optima, optimum in, in, a by using kind of non local information, okay? So what typically these things have, they have some kind of memory, there is some kind of learning component, okay? So this is essentially what the difference between this two things, one of them is going to guide you to the local minima and the other one is going to try to allow you to escape from the local minima. And, and tries to get to global optimality. Okay? And so, today, we're going to talk mostly about heuristics. And then we'll spend the next two lectures talking about metaheuristic, okay? So, so, one of the ways that you define legal moves, okay? So, and that drives also the heuristic. Is by lose, use, looking at condition of the objective function. There will be other things that we are going to look at. And you'll see some of them today. And you know, and in the next lectures. But essentially, what I'm going to show you now, are just condition of the objective function, okay? So local improvement, we already mentioned this, essentially, you want to stay such that you improve the value of the objective function, okay? So that's a strong condition. You have always to move to someplace which is better. Okay? Now, sometimes, there is no such neighbor, but there are neighbors that are different from where you are. Okay? Okay, obviously and these neighbors may not be you know, better than, than, than the current state, but they can be you know, equally good. And so it means, still be advantageous to move there because maybe from there, you can move to a place which is better, okay? So that's called No Degradation essentially. And what you do is you basically select something which doesn't degrade the value of the objective function. Okay? So very useful, used in many conditions. Okay? And is, it, you can also use that to in, introduce randomization. And we'll talk about that a little bit later. Okay? And then you can be completely you know, brutal and say ooh, you know, I can [INAUDIBLE] all the neighbors. Okay? So and we'll see some search heuristics here. That would actually do that. Okay? And so essentially, potentially everything is a neighbor. Okay? Of course we, we're going to, you know? Once you have something with that consider everything. You will have to have a selection function that does the right thing. Okay? So it's going to be a combination of what is legal and how does selection function work? Okay so with this some kind of properties are what you can do, okay? So now you have also one of the things that you will have to see is that you will have to, once you have the neighborhood and once you define what is, what is legal, you will have to decide how to explore this neighborhood. Okay. And sometimes the neighborhood is tiny, sometimes it's huge. So the way you explore this neighbor is, is important. Okay. So we will see various kinds of things. Okay. So one of them is best neighbor. You want to look at the neighborhood in it's, in it's, in it's entirety. And you want to select the best neighborhood. Lot of local search are doing things like this. But of course that means that you have to scan the entire neighbor route. And select the best, you know for selecting the, the best neighbor, okay? But this is one of the things that is very popular, okay? The next thing which is, which you can do is to say ooh, I'm not interested in exploring the entire neighborhood. I want to stop as soon as I find something legal, okay? And sometimes we call that you know the first, the first neighborhood. Okay? So you want to find something which is legal and then you know, that, that's sufficient. You stop at that point. The hope is that you don't have to explore the entire neighborhood. You can very quickly find the neighborhood that is legal and then you move there. And then you stop. Of course, you know, when you at, at some point you will have to explore the entire neighborhood to find out that there is nothing legal. But in a sense, what you, most of time you hope that you will only explore a subset of the neighborhood. So if the neighborhood is big. You can still use something like that. It will take more time if you try to do the best neighbor. And then we have this thing which is called Multi-stage Selection. And the key idea there is that, you want to preserve some of the greedy aspect, that's really important for you. But you don't want to explore the entire neighborhood because it's very big so what you do is basically split the neighborhood exploration in two parts. The first one is going to select part of neighborhood, so you won't explore the entire things. You will only select a subpart of it. And the second one, the second part is going to explore in it's entirety the rest of the sub neighborhood. Okay. And I'm going to give an example of this because it's very interesting and very useful in practice. Okay, now, now lets look a little bit about the best neighbor. Okay, so in practice you may have many different neighbors that are, that have the best value okay. And in those cases, randomization is very important. So you don't want to be in in many cases in local search. You don't want to be completely deterministic. You want to introduce this randomization component. And that allows you to explore the search in a more, in a, in a, in a more interesting fashion. Okay? So we'll talk about this much more at some point. But at this point here, considering the best neighbor there is something very easy to do. Okay? So you basically you know, you basically take all the best neighbors, so this have the, this are really the legal move that you want to go. And then essentially you want to select one of them, but you want to do that randomly, okay? And so what you do, if they are essentially, if the number of neighbor is cardinality of N and star, which are the best neighbors, you want to select one of them with the probability which is one over the size of those best But, this, this, best this best neighbor, okay? In the sense, what you do here is you compute all the best neighbor and then you, you basically choose one of them you know, in a, in a uniform random fashion, okay? And so, we will, we often do things like this because it gives you ways to actually not going always to the same place but it gives you more variety. Okay? So essentially you want to see best improvement you can prioritize the local search that I have given you at the beginning. By simply using an improved essentially using improvement as, you know, improvement as the, as the, the legal moose and then selecting the best one. Okay? So, if you select these things, you will have a local search. the legal moves are going to be the one where you improve the value of the objective function and then you always select the one which has the best value with the definition that I've given you here. Which basically means your computer's set and then you choose one of them randomly. Okay, so that's one of the things. So you could do similar things for the first neighbor in that particular case. What you do is essentially you take the first neighbor in the neighborhood exploring it in some kind of lexicographic order. Okay, and that's what you return, okay? And so once again the function can be very easy to compute it. What you do is you, you say all the legal moves are the one that improve the objective function. At the current state. And then, You want to select the first one which is legal, in a sense. Okay? So that's how you can parameterize this search. The generic local search that I gave you before, okay? So let me talk a little bit about the multistage heuristic. Because, you know, as I said, you know? Some of them are really useful in practice. And the motivation, as I said is you still want to keep the greedy aspect but you don't want to scan the entire neighborhood because for some reason, it's too large. And it's not a good compromise between, you know, the quality of the solution and the efficiency of the algorithm, okay? So we have seen one of those, okay. So one of them was essentially the way did the search for the Queens problem. Remember, when we did the Queens problems, every Queens. Could be associated with a violation, that's the number of all the queens that are currently attacking. And then we were basically looking at the queen that is the most aggressive, and we were basically moving it to a position where it was much less aggressive. Okay, so basically the position where it min, which minimizes the number of violation okay? So, what we need was two step, right? So, we selected only one queen and then we moved this value to the best, to its best position as far as decreasing the violations are concerned, okay? So in a sense, you know, this heuristic is, is sometimes called max/min-conflict. You select a variable which appear in the most violation. It's greedy. Okay, so greedy choice of the variables, and then you're setting the value for that queen/g. So a row, okay, for the column as a queen/g. Okay? Which result in the smallest amount of violations. Okay? And that's also a second step, which is greedy. But the first step, has already selected one queen/g. Okay, so in the second step we only look at one queen/g. Not all the queens, okay? Now a variation on this is is the original min-conflict heuristic. That was proposed by Steve Minton, and what you do here is you just select the first screen randomly. It has to have some violation, but you, you select it completely randomly, okay? And the you select the value for that queen which minimizes set of violations. So that's typically called the Min-conflict Heuristic. So the first step is randomizes, the second step is greedy. So two examples of Multi-stage Heuristics. You first select some part of the neighborhood, you know, Queen, and then you select all, you look at all the possible values and you select the one which is the best in the second stage for that particular selected Queen. Okay, now what would be the alternative to that? The neighborhood that you could explore are all the queens and all the possible move for the queens so you would require a quadratic neighborhood. Okay. And the next state, okay, the set of state obtained by looking at the current state taking any queen q, and any value v and looking at what that state results. It result into. Okay. And the key point is when you do that. You, you may have solution that are actually better than what I've just shown you, right? It's not necessary the queen which has the most violation which is going to decrease the violation the most. It may be a queen which has, you know, fewer violation but then you can reduce the number of violation tremendously, okay? So that's basically, you know, this is a quadratic neighborhood. It would, gives you the best local move. What we do is an approximation of this, right? By using essentially a first selection of the variables and then a selection of the value. Instead of considering the entire thing globally. Okay? So, the complexity here would be quadratic. Okay? All the pairs, for, all the columns and the rows. Okay? So, and, and, therefore, you have a, there is a price to pay here. It's essentially you know, you, you are proportional to the number of parts in the chessboard. Okay? One, we look at the min-conflict of the max min-conflict heuristic, this is a neighborhood which is used to explore in linear time, right? So we basically select a queen, okay that may take at most linear time and min-conflict, it's constant time. And then you have to select the value which is also looking at all the values right? All the values in the column, that's linear time. So, you know, constant plus linear or linear plus linear, it's linear time, okay? So, what you see here is a trade-off, okay? So, we won't have the best neighbor but we'll have a, you know kind of a greedy neighbor anyway. But we take only linear time instead of quadratic time so we have. We can explore many many more neighbors in a sence. Okay, and sot the kind of trade off that you often have in local search. Okay, so this multi-heuristics as I said, you know are useful. Okay, very useful. Okay, now think about it's you know, we saw you the consequening example. And remember we had all these cars on the assembly line, there were contraints on how many you know, how many units how many cars. How many options a production unit can put on a car, okay, in a row. And then essentially, we was basically scheduling all these cars on the slots, okay? And you know, the stars here are all the cars that are basically violating some of these capacity constraints, okay? And the neighborhood we selected was, oh, we want to take two cars, one of which has to be in violation and we would just swap them, okay? Now, if we ac-, if we want to have a completely greedy procedure, okay, for this particular neighborhood, okay. So, and so it, it's going to be a quadratic neighborhood, right? So we going to take, we can scan every slot in the assembly line and then swap it with all the other slots in the assembly line. And that's a lot of swap right. So if we have an assembly line with say, let's say 300 you know, cars. This would be exploring about 45,000 you know, configurations. So it's going to take awhile to do that, okay? So a multistage neighborhood would just say ooh, I'm going to select one car, okay. So It's kind of a linear kind of your assembly line, okay. And then you're going to say ooh, which other car can I swap? It's another linear you know swap of the, of the neighborhood. And that's essentially a much smaller neighborhood, right. It's like you know, 600 you know, at most 600 you know, operations that you need to do. So it's linear in the size of the assembly line. So once again you have this tradeoff here. You know, I can get the best move or I can get a very good move. But much faster. Which one is the best? Well, that will depend on the problem but you have to consider these options when you're [INAUDIBLE] designing a local search procedure, okay? So that's, you know, to give you a sense, you know? you can take the best neighbor, you can take the first neighbor, you can take something which is in between, in a sense, which is, you know, taking something which is greedy but we've a multi-stage approach. So, what I want to talk about now is random work. Which is a completely crazy idea in a sense, but their are, there are applications which, this is the thing to do. Okay? So randomization is what? You want to select a neighbor A completely at random. Okay? And then you have to decided whether to accept it, okay? And so, some of them are going to accept the move if its improved or you can use the Metropolis algorithm that I will talk about in a later one. But essentially what you're going to do is select a neighbor randomly and then decide if you accept it. Using some time of criteria, right? And so essentially let's look at the first one, which is random improvement, what you do here is Is that, you basically look at the neighbor, okay? The entire neighborhood and you take one neighbor with you know, some probability which is, essentially you've seen that all the neighbors can be selected with same probability. You take one randomly, completely randomly, and then you look if it improves the current solution, if it does, you move to it, okay? If it doesn't you stay in the same state. And you iterate these things, okay? So, so this can be actually very effective, okay? In some part of your, kind of local search, okay? And there are var, various cases where this is effective and one of them is when the neighborhood is really, really large. Okay, so remember this traveling tournament problem, okay? So we had all these teams, kind of the baseball teams. That had to meet with you know, play against every other team twice, you know, it was a round robin tournament. And so you would play some games at home, then move, you know, play some games away, then come back and play these things. And the goal was to minimize, essentially, the travel distance. And so you had these constraints making sure that the team don't play too many games in a row at home or away. And then you had basically, this optimization, this objective, you know, this objective function, which was global and therefore difficult to optimize. Okay? And so what we saw is that there were plenty of moves that we could do. Right? So we could swap homes, swap teams, swap rounds and then the partial version of these guys. Okay? And some of these neighborhoods are actually pretty complicated. They are you know, let's say end cube end cube moves the, in, in some of these neighborhoods where n is the number of teams. Okay? And, and, more, more, more, more important you know equally important in a sense /g. Some of this move were affecting the entire schedule. So, you had a lot of operation to carry it out. Okay? So, this was essentially swapping swapping the [UNKNOWN], swapping the teams here. And so you know you would affect the large part of neighborhood there and then you need flip some of these to the rest of feasibility and so what you see here in color essentially in all the things that have been moved during that particular, that have been changing that particular move. When you look at somethin glike this you have many, many ,many neighbors and everyone is going to affect the entire scheduleso they take long to evaluate. So you just can't really do very effectively a, a best neighbor. you know, a, you know a best neighbor exploration. Because that would take a lot of time, and the benefits are not really very clear at that point, okay? So what you can do instead is just select one of these move randomly, see if it improve your schedule. If it does, yes, you take it. If it doesn't, you just say in the same state, pick another one, and so on. Okay, so the best research that I've shown you, we talked about it earlier, you know the, the, the TTP, the traveling time on problem, were based essentially on a random log. And I will tell you also what is the metaheuristic and what is a heuristic to decide whether we accept a move or not. But it was basically using completely random move at every iterations of the search, okay? So this is essentially the highlight of the presentation I want to give you today, so we saw essentially the generate search, and how you can parametize it with heuristic and metaheuristic. But I haven't shown you the metaheuristic yet. And that's what we're going to talk about next time. But I haven't shown you the metaheuristic yet. And that's what we're going to talk about next time. Okay? See you next time. Thank you.