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.