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?