0:00

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?

Â 13:43

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.

Â