So, welcome back, so this is Local Search Part IV, and we are not yet there, there are many more, but this lecture is really interesting. And the reason it's interesting is that we're going to look at optimization under constraints and how we can do local search on this. And why is it interesting, because there are many, many, many options. There are many ways you can actually approach this. And, and there will be different trade-offs in the complexity of the neighborhood and the complexity of the objective function, the complexity of the search. So we're going to illustrate every one of these, these, these various possibilities using graph coloring. Which is very simple to conceptually, but it's a very, very hard problem, in, in to solve very large instances. Remember, you know, graph coloring, this was the city of Europe that we saw when we were doing constraint programming, okay? So we can model that as a graph, right? So every country would be essentially a, associated with a vertex, and then there will be an edge between these two, these two vertices. If the two countries are adjacent, okay? And know that the, the goal of the application would be to find a coloring of this graph, such that every two vertices which are adjacent are given a different color, okay? So that's graph coloring at a high level. Now this is a tiny, tiny, tiny little graph. So what we are really going to be talking about here are really huge graphs, okay? So this is two 250 vertices. It's er a graph which has generated randomly, and the probability of having an edge between two vertices is is, is 10%, s, is .1, okay? And the key, and so you see, can already see how dense it is, okay? And one of the key things about graph coloring which is nice is that random products are typically very hard. So if you take, let's say, you know 250 vertices, you know, .5 density, that's a really difficult problem, okay? So this is the kind of things that we want to tackle, okay? So, color me this graph, and finally the smallest number of colors, okay? To color this graph, okay? So there are two aspects of course. so one aspect is that we have to minimize this number of colors, okay? We want to as few as few colors as possible,but there is also the feasibility access. At any point we want this coloring to be legal, two counts, two nodes, two vertices that are basically adjacent to each other should be given a different color. So you know there is a trade off between these things and how we're going to deal with them, okay? And that's essentially the topic of this lecture. How can we balance the fact that we want to decrease the number of colors but we want also to get a feasible solution, okay? And so essentially the way we're going to combine that in, in Local search, there are basically three ways. The first one is just to say, you know, what I love in life are feasibility problems. So I want to reduce that problem to a sequence of feasibility problems. I only want to solve feasibility problems. And I will show you how to do that, okay? Then the other things, and this is essentially what we have done already for the traveling salesman problems and also for the where else is location. We, we can decide that we will stay in the space of feasible solution. We will only look at legal colorings, so no violations of the constraints, ever, okay? And you'll see that this is actually raising some interesting challenges, and, and we'll see how we can address some of them, okay? So, then essentially, the last thing is like, well, I don't want to look at this as a feasibility problem, okay? Because it's both a feasibility and optimization problem. I don't want to stay, you know, in the space of feasible solution, because once again, I want to deal with both aspects. And so what you're trying to do is basically look at both aspects simultaneously, and you will consider both feasible and infeasible configuration. So you will be in a larger space, okay? So you will both consider feasible and infeasible solution. And we'll try at the same time to decrease, you know, to satis-, to minimize the objective function, but also to find feasible solution. And I will show you how we can do that. And in graph coloring, there is a beautiful way to do that, which is nice to, really nice to explain, okay? So let's start with looking at the optimization as feasibility, okay? So I told you we are obsessed with feasibility, every optimization problem, we want to take it and view it as a sequence of feasibility problem. How can we do that in graph coloring? You know, this is what we do. We start, we have a feasible sol, we have a feasible a feasible solution. We have a certain number of colors. So, you can take a Greedy Algorithm and just try to find a feasible solution. And let's say we have K color so that brought you a solution, okay? So, once we have this k color, we say okay, so the next problem should have at least you know, one fewer color, okay? So, we want a solution, let's say with k-1one color, okay? What do we do? Well, we take all the vertices which are, you know, let's say color with color K and we basically replace them with a color, which is, from one to k-1, okay? Now what do we have? The problem is infeasible. We have plenty of violations, right? Or, maybe not. But, we have, you know, most likely, we'll have violations. So what you do is, we say, okay, so now the goal is to find a feasible solution with this k-1 colors, okay? And then obviously once we find a solution to that okay, so we k-2, k-3 and so on and so forth. Until we cannot find a feasible solution to our problem in which case we know that we have an optimal solution except that here we'll be using local search. We'll have no guarantees, okay? So, the key question here is obviously, okay, this is easy to do but how do we find a feasible solution. Okay, when, you know, how do we, you know, find a feasible solution, let's say, with k-1 color. And the way you can do that is essentially what we did in the first two lectures on, on graph coloring, right? So you look at the problem, you look at the violations and you try to minimize these violation, okay? So we have seen how to do this, okay? So, we just do that, okay? And that's the first approach for solving optimization problems, okay? Very much like the way constraint programming solves optimization problems. So you view that as a sequence of feasibility problems. At every one of these steps, you try to minimize The number of violations and then you have a feasible solution with k-1, you do the same with k-2 and so on and so forth, okay? So, so that's one of the, that's the first approach. The other approach is to say, you know, I don't like feasibility problems. I'm always going to assume that I'm feasible, okay, and I'm focusing on the objective function only, okay? That's what I'm obsessed about, okay? So, what do we need in graph coloring, okay? So the objective function is going to be minimized in the number of colors, and you assume that all, all the, all the, all the, you know, all the, the configuration is basically satisfying all the constraints, okay? Now, how to guide the search, that's the problem right? So because essentially it's like in the magic square example, right? So now we have all these legal colorings, okay? And now we're going to change the color of one particular vertex, but how is that going to affect the number of colors that we have? Most likely, it will not do anything right? Because if you could remove that color in you know, in one step and get a solution, that would be kind of a very unlikely event. And now you probably have a lot of colors with k-1 and you will have to get rid of many of them. But changing one is not going to change the number of colors. So the numbers of colors is kind of a very close way at looking at the objective function. So what you have to do, is essentially change the way you think about the the problems and objective function, okay? And this is where introducing the concept of color classes is useful, okay? So essentially what I'm going to say is that color classes i, Ci is going to be the set of vertices, which is color, with color i, okay? So essentially Ci is all the vertices in my huge graph, which I color with color i. Okay, C2 is all the vertices color with two, okay. And now to drive the search, I'm not going to look at how many colors I'm using. I'm going to look at the proxy, an indirect way of trying to minimize the number of colors, okay? And the way to do this is to look at the color classes and try to have huge color classes, right? Because, you know, when you have very few colors, typically you have large color classes, okay? So, this is the optimization function that we are going to use. It's an indirect objective function. It doesn't directly minimize the number of colors. It's what instead, what it's trying to do is to minimize the square of the sizes of the color classes, okay? So, in a sense, what I'm saying, I want big classes, I want big classes, okay? And so, think of it, you know, if there is one class with one color, and another class with 10,000 ver, you know, cal, 10,000, one vertice, one vertex. And another class with 10,000 vertices, if you move one, you know, from the other, from the large class. You're going to have really big increase in the, in the object, in the, in this objective function, where you maximize the size of the classes, okay? So this is what we're going to do, okay? Now once you do that, okay? So one, one of the problems that you may have is that it may be actually very difficult to move from one legal coloring to another one. You may be really, really heavily constrained by the fact that you're working in the space of legal coloring, okay? So, in a sense, in many of these applications, okay? So, when, once you are trying to keep the, the constraints feasible. You have to think of a neighbor-route that allows you to actually explore legal colorings in a reasonable fashion. And, and move, you know to places, okay? And not being stuck in a popular configuration where there is no way to move because I would violate at least one constraint, okay? And this is an idea that you can actually use inside inside coloring, okay? So, it's a richer neighborhood which is exploiting the stretch coloring much better, okay? This is called Kemp Chain, okay? So let's look at two color classes here, you have the, you know Ci and Cj, okay? And, and, and, and look at one of the vertices here, v, okay? And assume that you want to change the color of v, you know, to blue, okay? It's red right now, it has to go to blue, okay? Now it's very diffiuclt to do that right now, right? Because essentially, essentially, what you see is that v is connected to these three vertices, which are already color blue, okay? And therefore, if you color v to blue, you will have three constraint violation, and you can't do that, right? So we are in the space of legal colorings, okay? So what are we going to do? Well, an idea would be to say, oh, what I can do is take this guy and move it to the other side. But then I take these 3 guys which are blue, and I color them red, okay? So these guys have no violations with, you know, no violations between themselves, so you move them together, okay? But then what is the problem? Okay, so this guy here, you know, is connected to another guy which is red. oh, if I move this guy to the other side I have to, to this guy, and move is to the blue side, okay? Oh, but this guy is also connected to this blue guy, so I have to move this blue guy on the other side and then move these red guy to the other side. And that's the idea of Kemp Chains. So, you look at these strongly, these connected components and you'd taken all of the components that are connected there and you move them. You move the red to the blues and the blues to the red altogether, okay? So, you basically select all of these connected guys, okay that you, that you see, okay? And this is basically the various componensts, the various vertices here that are connected. And you take the red one, you make them blue. You take the blue one, you make them red, okay? And you swap them, essentially. And that's what you get. And now, magically, I mean, not magically, by design, right? So what we have here is that all the vertices that are blue, you know, have no violation. All the vertices that are red have no violation. And obviously, you're still at the length between the red and the blue. These are basically the same length than, than before, okay? So this is a much richer neighborhood, right? So you take a vertex, okay? And you take a color class in which you want to move that vertex, and then you find its component and you swap these two sets of vertices, okay? Much richer neighborhood, but the beauty, the beauty here is that we are staying in the feasible space, okay? So all the colorings are always going to be legal, and therefore we can only focus on the objective function. The same way as I have shown you when I was just swapping the color of the [UNKNOWN] vertex, okay? So it's a much richer neighborhood, I can explore many more things. Okay so the neighborhood is much larger. And, therefore, in general the quality is going to better, okay? So we have to deal with the efficiency side, but in a sense the neighborhood by definition is going to be better. But you're still feasible, and this is, this may be very interesting, okay? So, so, so we have seen two approaches so far. The first one was looking up you know, the, the first one we were obsessed with feasibility. And we were trying to solve the sequence of feasibility problems. In the second one, we were obsessed with the objective function. And we always stayed feasible and tried to improve the objective functions, okay? The third approach is to say okay, so I'm not obsessed by anything. I'm going to look at feasible and infeasible coloring. I can do both feasible at one some, at some point in the search and sometime it's feasible as well, right? And so now the search will focus on two things at the same time. We will have to focus on decreasing the number of colors and also we'll have to focus on decreasing the violations on the constraints, you know? Trying to ensure feasibility and find a legal coloring, okay? So, how do I do that? Typically what I want is an objective function that balances two things, okay? So I want to have something which looks at the object, at the objective and weight it, okay? And I want to have something which look, at, the, the, the violations on the constraints and also you know, is associated with a particular weight. And what I minimize is the overall thing, okay? So in a sense, sometimes I'm favor the objective function and sometimes I'm favor, you know, the feasibility. And the objective function is going to basically drive me to something which is good in both sense, okay? So, what is the neighborhood that I'm going to, you know, be concerned with here? We're going to take a very, very simple neighborhood. This is only changing the color of a vertex, okay? And then I need to introduce another concept so that we can express the drawing objective function nicely. I'm going to talk about Bad edges, okay? And a Bad edge is simply a net between two vertices, okay? Which are color with the same color. So these two vertices are linked, okay? They have the same color, so the edge is, is called a bad edge, okay? So it's a violation, essentially, okay? And I'm going to denote Bi, okay? The set of bad edges, which are colored with color i, okay? So, I have two edge, so for having a bad edge, I need these two vertices to have the same color, okay? If you know, that edge is considered a bad edge of color i, okay? I look at all my graph, and I look at all the vertices which are connect to all, all you know, the vertex, the two vertices that are connected an edges, by an edge. And are colored by i, I that these are you know, basically violation. And Bi is a set of those edges, okay? So concept of bare edges, okay. And know essentially what I want to do is find a nice way of expressing this objective function, okay? Once again, neighborhood is changing one color, okay? Now I have to focus on the objective function. I'm going to use exactly the same thing as, that we have done in when we were in the feasible space. I'm going to try to maximize the square of the sizes of the color classes, okay? So that basically drive me towards, you know, coloring with very few colors. And then, I have to remove the violation, okay? And the violation can be very, expressed very simply, right? So, what I want to do is to minimize the sum of the bad edges, okay? So, the, the, the sum of the sizes of the bad, the, the, the set of bad edges. And that's what you see over there. So, what I have to do is, maximize this, minimize this, and then I can combine these 2, okay? So one of, and the way I'm going to do this is by using this objective function, okay? So, so it takes the two aspects that I've mentioned before, okay? So we are basically here, you know maximizing the sizes of the color classes. Nothing fancy there, okay? I'm, you know, since I'm minimizing, overall I'm minimizing okay? So maximizing this is basically a minus of this, okay? So that's easy. And then the other things that you see here, is essentially this is the part which is minimizing the violation, okay? And instead of simply the sum of the sizes of the bad edges the, the you know the set of bad edges. What I'm doing here is multiplying this by the size of the color classes of these edges and then multiply the whole thing by 2, okay? Now you may say this guy is completely crazy, okay? But essentially there is a good reason to do this, okay? So this objective function has a beautiful property, okay? So, and before I tell you what that property is, okay? So one of the things you have to think about is. When we are trying to minimize these two components, well to minimize these two components together, okay? So let's say the objective and then feasibility, okay? The local minima, have no guarantees whatsoever on how, what this objective function is going to be. And how the very, the two aspects are going to be combined together, right? So you have no guarantees that when you reach a local minima, okay? So you actually have a feasible solution. Okay, a feasible coloring, okay? So in a sense, you know, you have, you don't know at that point that, that this minima is giving you a solution to your problem, okay? So what this objective function here does for you is that it guarantees that local minima are going to be legal coloring. Wow, that's, that's amazing, right? So I just minimized this function using local search. I get to a local minima and because of the design of this function you are guaranteed that, that minima is going to be a low, a legal coloring, okay? And therefore you know, you can just run this thing, you know, find the local minima or find a bunch of local minima. And all of them will be legal coloring and you can take, you know, you can take one of them, okay, as your solution, okay? And why is this true? This is the proof, it is a very simple proof, okay? And the key idea of the proof is okay, so let's assume that I have a coloring, okay? you know in color class C1 to Ck, so I have K colors, okay? And I'm going to assume that I have a violation, okay? So that means that one of the Bi is not empty. Okay, so I have a bad edge somewhere. And let's assume that this is color i, okay? And what I'm basically going to show you is that this particular configuration, okay, is not a local minima. It cannot be a local minima because I can improve it. I can improve it by changing the value of a single vertex, okay? So, what I do, is that I'm going to add a new color, k+1, and then I'm going to select the bad edges in Bi. And I'm going to select a vertex in that particular, in that particular edge, okay? And I'm going to change the color of that vertex from i to k+1, okay? and I'm going to show you that the value of the object function is going to decrease, and therefore this cannot be a local minima because I do this local move. And I have a better solution, okay? So by definition therefore all the local minima are going to be legal colorings, okay? So how do we do that? Well, we look at the objective function, right and only thing that we have to do is to see how it varies, okay? And typically there are these two, you know there are these two parts of the objective function and we're going to analyze them separately, right? So how does it vary? Well, with the left term, okay? So if we go back, the left term here is basically the, the term dealing with, feasibilities, okay? So this, this term essentially varies in this particular way. So this is the value before the, the, the local move that I'm making right now. This is the value after, okay? So what I do there, is that I decrease the bad edges by one and I also decrease the size of the color classes i by one. Because I move the color to k+1, okay. And so therefore the number of bad edges for this, this is the number of bad edges that I will get, okay? Of course the new edge, you know the, the, the vertex that I selected will have no violation because it's a new color that nobody else is using okay? So I do some algebraic manipulation and you know that this thing is going to be you know, basically the, the decrease in this left term is going to be greater. Actually is going to be equal to two times the size of Ci, okay? So you know this, this is how the left term is basically varying, now you look at the right term. The right term is, is looking at basically the objective, the objective part, the size of the color classes, okay? Now it's, you know, in the formula, it's, it's, it's negated, right? So what we, what we have to study is how this, you know, right term increases because there's going to be a decrease in the objective function. an increase in the well, it's going to be an increase in the objective function. So what we do there, we take, you know the square of the, the class is i because that's the class which is decreasing. The new, the new configuration will have one fewer vertex there, but will have also one more color classes which has a value of 1. You know, you manipulate this and you get what two C you know size of Ci minus 2 and that term actually is smaller than the term we saw over there by 2. So we know that the objective function in this particular case is going to decrease at least by 2 [SOUND], okay? So which basically means that if your coloring is not legal, I always have a way to decrease the objective function by 2. And therefore this is not a local minima, okay? So the beautiful objective function that I've shown you is this beautiful property, okay? That you know, it will give you every kind of local minima will give you a local coloring. So, once you search terminate, you don't have to worry. You will have a solution to your problem, with hopefully a small number of colors, okay? So, essentially, let's try to summarize what we saw here. Is when you have an optimization problem, okay? Which combines the objective function in a set of constraints, there are 3 ways to look at it. Solving a sequence of feasibility problem, or focusing on the objective function and always staying in the feasible space. Or trying to basically balance the search in the feasible space and the infeasible space. And hopefully, you know, having some properties, or some techniques, that will guarantee that the local minima are going to be feasible solutions. So the rest of the lecture is now going to focus on some more complex neighborhoods and also on hard to escape local minima, okay? Thank you.