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.