Welcome back. This is discrete optimization, again and
we are moving to the second computational part for optimization which is called
local search. This is the outline for today.
We're going to start with basic interaction to our local search, and then
we'll cover very simple local search, which is called max/min conflict.
To introduce most of the concepts that we will be dealing with in the next couple
of lectures. So, a couple of years ago when my son
was, you know, very young, so I gave him the eight queens problem to solve, okay?
So I wanted to see how he would just approach it.
And so this is what he did, he took all these queens, okay, that I gave him, and
he put them on the chess board. Okay?
And then what he did was started moving these queens.
Okay? Trying to find a configuration where none
of the queens were attacking each other. Okay?
So, he didn't try to prove the search space, or try to extend you know, a
partial solution. He just moved the queens around.
And this is exactly what local search is about.
So, what you're going to do is you're going to move from configuration to
configuration, by doing local moves. So, moving the configuration from it's
current state to a state which is very close to it, but you know, but changing
it a little bit. In the hope of getting closer to a
particular solution. Okay?
So local search, okay, is basically working on complete assignments of values
to the decision variables and then essentially is modifying those, those,
those assignments. Okay?
So is there a different from constraint programming?
Well, essentially, what we were doing, we're working with partial assignments,
and trying to see if we could extend them.
And, to make sure that we could extend them, we were trying to prune the search
base as much as possible so that we would not try to extend them with a value
which, which was not feasible. Local search is way more brutal, okay?
So we accept that we're going to violate some of these constraints.
And then we just try to eliminate those, those, those, those violations as we
proceed, okay? So, how to drive a local search, okay,
there will be different things that we can do, okay?
And it depends essentially on the nature of the problem.
If you have a satisfaction problem, what you will do is you will always start with
an invisible configuration. Otherwise you would have already a
solution and therefore there would be no problem to solve.
And then what we are going to do is start, you know, move from this
infeasible, you know, configuration toward, you know, feasibility.
And trying to essentially make this configuration more and more, less and
less infeasible in a sense. in pure optimization problems the only
thing that you have is an objective function, you have no constraints.
Okay, and what you are trying to do is essentially go to the optimal solution,
so you start with a sub-optimal solution. A local search is going to try to move
progressively towards optimality. And then, you have constrained
optimization problems which are the most complicated, of course, you have both
constraints and optimization. And I will review some of the options
later on, once we have seen above satisfaction and optimization problems.
Because there are many ways to actually try to address those problems in low
consumption. Okay?
Now lets look at satisfaction problems first and how to drive the search towards
feasibility. And the key idea here is essentially we
have this, you know feasible, well this satisfaction problem and we will
transform it into a sequence of optimization, into an optimization
problem. Okay?
So we use the concept of violation. Essentially, at any point, we have that
configuration. Okay, basically this assignments of
values to the decision variables. And we know that their are a bunch of
constraints that are not, that are violated, okay?
We can count them, for instance. And then what we can try to, and this is
only one of the ways to do it, but we can try to minimize the number of violations
to these constraints. So we want to move from a configuration
to another configuration where there are fewer violations.
Okay? Now how do we do that?
Well we have to decide what is a local move.
And once again, and we'll see that in the next couple of lectures, there are many
ways you can move from one configuration to the next.
The simple things is just to select a decision variable and change its value.
Okay? So very simple move.
Okay? Now once you have defined all moves that
you can take, you have to design the one that you're really going to select and
execute. Okay?
And once again there are many choices, and we'll see many different strategies
over the next couple of lectures. But the thing that we are going to do,
the, the approach we are going to pursue today is simply a maximum conflict.
approach which is essentially a slight generalization of the main conflict
heuristic , which has been very successful in a variety of problems,
okay? So what is the max/min conflict heuristic
doing? Essentially what we do, is choose a
variable that appear in the large numbers of violations.
So, we look at the variable which, which is really violating a lot.
All those variables really violating a lot of constraints.
And then what we try to do is to change the value of that constraint so that you
decrease the number of violations the most.
Okay? So, let me just trade that.
Okay, so this is remember this is the constraint programming model for the, the
queens problem. And what is interesting to see on that
particular model are all the constraints that you see over there, right.
So, some of these constraints, once you assign some value to the variables, are
going to be violated, are the ones are going to be satisfied, okay.
Now visually, this is what this looks like, right, so when you look at the
part, so you see. You see here, you know there will be a
constraint which is violated. This is another constraint which is
violated, okay? So now when we look at the max/min
[UNKNOWN], what we want to do first is to compute, you know, the various
violations, the constraint violations in which are the particular variables
appear, okay? So we look at this particular queen here
and now we look at the constraints that they are violating and, of course, what
we have to do is to look at, you know, the vertical, the diagonals and the
horizontal lines, okay? So in this particular case, we see that
this particular variable appear in exactly one conflict, right?
This queen is attacking that one. Okay?
So we move to the second one, okay, second queen.
Okay, and what we see there is that this queen attacks that queen, and it attacks
this one, and so this particular queen appears in two violations.
Okay? And we can do that for all the Queens.
So this is another queen which is basically having two violation.
The next one is very aggressive has three violation, and so on and so forth.
And so essentially what you see here are all the vi, the violations that these
variables, appear ins, ins, into, and what the number that you see over here
essentially is the total number of constraints that are violated, okay?
Now, the first thing that a maximum conflict heuristic will do is take a
queen which appear in the largest number of violation.
Okay? So you have a queen here which is very
aggressive and appearing at three violations.
That's the queen that you're going to select.
Okay? So that's the first step.
Now we have the queen that we really want to move because this queen is very
aggressive. Okay?
So what do we do? So now we have to choose the value that
we going to to assign to that particular queen.
And what we can do is decide, okay so what happens if I move this queen to that
particular position, okay how does that change the constraint violation?
And what you can see in this particular case is that instead of having three
violations, we would have only two, so we are attacking these two queens.
And then you can do the same thing for the next queen.
Here in this particular case the queen is still very aggressive and has still three
viola, three violations, okay? And then we continue doing this
essentially for everyone of the possible position for that part of the queens.
Okay, and what we see at that point is that, you know, if you want to reduce the
violation the most we have to choose one of these values and we can randomly
choose, let's say the first one here. Okay, and at that point what we do is we
place the queens at that particular position, so that's the local move.
We chose the queens. We chose a new position for the queens
and we you know, we performed the move. Okay?
So at that point we have a new configuration and we can redo all the
computations that we have done. We can find that there are five
violations overall. We can find the number of violations in
which all the queens are participating to.
And then we can decide, you know, we can select the queen.
One of the queens participating in the most violation and start deciding where
to move it. In this particular case only one of the,
of the move is going to decrease the number of violation, so that is where we
move the queens. We have a new configuration, so what do
we do? Exactly the same thing.
Now we have four violation. We reduce the number of violation by one.
We recompute the violation so the variables, you know, we select the one
which appears in the most violation, and we start moving it again at a position
that will decrease the number of violations.
And we keep doing this, now we have, we move another queen.
And we can, we have three violations now. We continue moving this queen again, we
have another queen which has two violations.
We move, we decrease the violation by one.
We keep doing this, another queen which is violated by one, we decrease the
violation to one, and then finally we will be able to reduce the violation to
zero, and we have a feasible solution. OK?
So what is important to see here is that essentially we start from an infeasible
configuration which has a number of constraint violations.
And we try to move to, you know, configuration which have fewer and fewer
violations. And at every step, we try to do that by
selecting a queens, in this particular case, which, which is, you know,
appearing in the largest number of violation, and moving it to a place which
decrease the violation the most. This is just one of the possible
strategies. We'll see many strategies in the next
couple of lecture but this is essentially illustrating the concept behind local
search. Okay?
So so in a sense the way to think about local search is that you have an
optimization function. Okay?
That the, an objective function that you are trying to optimize.
And then what the local moves are doing is defining a neighborhood.
That's essentially the configurations that are close to the configuration that
we are considering right now, okay? So, in the sense that the neighborhood
is, from a particular configuration, it's going to give you a set of
configurations. And that's the places where we can move.
Okay? So, in the particular example of the
queens problems, the neighboring configurations were simply the ones that
you can reach by selecting the, one of the queens which is most violated, and
moving it to a position which decreased the violation the most.
Okay? So, in a sense you can think of local
search as a graph exploration. You start, you know, from a particular
point, and then you start moving to configuration, to another configuration,
and so on. And you try to go to configuration which
are, you know, more and more feasible in a sense.
Okay? So that's what we do.
Okay? So the concept, the key, the key concept
in local search is the concept of local minima.
Okay? That's what a local search does.
It gets you a local minima. And what is the local minima?
It's a state. Inside the configuration space where,
wherever you move, wherever you're neighbors are, okay, they are going to be
worse off than where you are. So it's a position where when you look at
every neighbor N okay, to the configuration C that you are conf, that
you are considering right now, the value of that objective functions of that
neighbor is going to be greater than the current value of the objective function.
Okay? So essentially.
You know, you are at that point, wherever you move, you are going to get worse, or
at best, you know, as, as good as you are right now.
Okay? So in a sense, the local search that you
know, the, the basic kernel of a local search, is going to select a
configuration seed, initially, using some method.
Then compute the neighborhood, okay. So that's a set of the configurations.
Well if you've got a computer set I of all the neighbors that you can, that you
can reach, and which are better than the configurations that you are in right now.
So we look at essentially all the neighbors which are basically decreasing
the value of the objective function, okay?
If that set is not empty you select one of these configurations, apply it, and
then you recompute the set of configuration in which you can move to.
Okay? So basically, you know, local search is
this kind of iteration where you move from one position to a better position,
and you keep doing that until you reach a local minima.
Okay? So local search, you know, gives you no
guarantees. Okay, so the only thing that it's
going to give you is a local minima, that local minima can be arbitrarily bad, or
arbitrarily good. Okay, so one of the things that we'll see
in a lot of the lectures later on is how to escape this local minima, or to try to
find local minima that are of high quality.
Not getting stuck into a poor quality optima and there are many, many ways to
do this, and but we'll talk about this later on once we have seen many of the
concept behind local search in itself. So for the moment we'll do this greedy
local such algorithm, which always trying to improve and gets stuck at some point
in a local minima. Afterwards, we'll see how to escape.
Okay? Now in satisfactions in satisfaction
problems what we saw is that the function F is actually minimizing the number of
constraint violations. Okay?
And usually when this function reaches zero, we know that we have a feasible
solution. If we get stuck in a local minima, which
is a value higher than zero, you know, the solution that we found is not
feasible. It's, the configuration that we found is
not a feasible solution. Okay?
So, there are many ways to measure this constraint violation.
And once again, this is a topic that we will return to, but what we have done so
far is basically looking at the constraints, and deciding if the
constraints is violated or not. There are other ways to actually measure
these violations. You can consider how violated that
constraint is, and we'll talk about that later on as well.
and the variable variations that we actually studied in this, in the, in the
examples in the queens example, we're essentially counting the number of
constraints. That were violated and that the variables
were, was participating into. So that's essentially the basic
introduction to local search. We're going to go into more and more
details in the next couple of lectures. Thank you.