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.