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.