Now that we've seen a concrete example of 
Local Search in the specific context of 
the maximum cup problem, let's move 
toward talking about this technique more 
generally. 
So lets think, abstractly, about some 
computational problem. 
Lets say there's a set X of the candidate 
solutions to this problem. 
Maybe you want to search whether or not 
their exists a solution with a given 
property, maybe you want to find the 
solution which is optimal, in some sense. 
What are some examples? Well, in our last 
video x was the cuts of some given graph 
g. 
Other examples would include the tours of 
an instance of traveling salesmen 
problem, or perhaps the possible 
assignment to variables in some 
constraint satisfaction problem. 
A fundamental ingredients to the local 
search approach is the definition of a 
neighborhood. 
That is, for each candidate solution x in 
the space of all possible solutions X, 
you need to define which other solutions 
that are y, are the neighbors of x. 
Let's look at some concrete examples. 
In the maximum cut problem last video, we 
were implicitly defining the neighbors of 
a given cut to be those cuts you can 
obtain from the given one by moving a 
single vertex from one side to the other. 
If you're taking a local search approach 
to a constraint satisfaction problem, 
something like 2 SAT or 3 SAT, a common 
approach is to define 2 variable 
assignments to be neighbors, if and only 
if they differ in the value of a single 
Variable. 
So, for the Boolean case, where variables 
are either true or false, you're going to 
define 2 assignments to be neighbors, if 
you can get from one to the other, by 
flipping the value of a single variable. 
For the travelling salesman problem, 
there's a lot of sensible ways to define 
neighborhoods. 
One simple, and popular approach, is to 
define 2 travelling salesman tours to be 
neighbors. 
If and only if they differ in the minimum 
possible number of edges. 
If you think about it for a second, 
you'll realize that the minimum possible 
number of edges that 2 TSP tours differ 
in is 2. 
So, for example, in pink I have shown you 
2 neighboring TSPs. 
P tours, the first tour has edges from u 
to v and from w to x, but by contrast the 
second tour has the crisscrossing edges 
from u to x and from v to w. 
All of the other edges in the 2 tours are 
the same. 
Once you've identified the space of 
candidate solutions to your computational 
problem, and once you've settled on a 
neighborhood for every candidate 
solution, you're in a position to run a 
local search. 
Local search just iteratively improves 
the current solution, always moving to a 
neighboring solution, until you can't 
improve things any further. 
I'm going to specify here a highly under 
determined version of the local search to 
highlight the number of design decisions 
that you've gotta make if you really 
want to apply local search to a problem 
in your own projects. 
We'll talk about the possible 
instantiations of the different design 
decisions in the next couple of slides. 
So, for starters, you have to initialize 
the search with one of the candidate 
solutions, some little x. 
How do you pick it? Well, there's a 
number of approaches, we'll discuss that 
in more detail in a sec. 
Now, just like in our maximum cut local 
search algorithm, we take the current 
solution, whatever it is x. 
We look for a neighboring 1y, which is 
superior. 
If we find such a y, then we move to that 
superior solution. 
If there is no superior y, we're locally 
optimal. 
And then and we just return to the 
current solution. 
Our local search algorithm for the 
maximum cut problem, that we discussed 
last video, is in fact an instinctiation, 
of this generic procedure, where the set 
X of all solutions, is just the cuts of 
the given graph. 
And, 2 cuts are defined to be neighbors, 
if and only if you can get from 1 to the 
other, by moving A single vertex from one 
group to the other. 
And that algorithm, as we are here, we 
just started from some arbitrary 
solution, some arbitrary cut. 
We repeatedly searched for a superior 
neighboring solution. 
That is we tried to see if there was a 
way to move a vertex from one group to 
the other to get a better cut. 
If we found such a superior neighboring 
solution We iterated from that better 
solution, and then when we couldn't 
iterate it any more, when there were no 
better neighboring cuts, we just halted 
and returned the final result. 
You can apply this generic local search 
procedure to other problems in exactly 
the same way. 
As an example, think about the traveling 
salesman problem. 
Let's say we define neighborhoods like we 
did on the last slide with 2 tours being 
neighbors if and only if they differ in 
exactly 2 edges, n - 2 edges. 
Are in common. 
What do you do? You start from some 
arbitrary traveling salesmen tour, and 
now you iterate. 
You keep looking for a neighboring 
superior solution that is from the 
current tour,. 
You consider all tours you can reach by 
changing exactly two edges of the current 
tour. 
You check if any of those end choose 2 
solutions have strictly smaller costs. 
If any of them do you iterate from that 
new superior solution. 
When you can't iterate anymore, when all 
of the neighboring solutions are at least 
as costly as the one you're working with, 
that's a locally optimal tour and you 
return that as your final output. 
And the rest of the video I want to 
continue discussing local search at a 
high level talking about some of the 
design decisions that you've got to make 
as well as some of the performance 
characteristics you can expect. 
After we finish this high level 
discussion we'll move on to some videos 
on another concrete example of local 
search. 
Specifically to 2 SAT, a specific example 
of a constraint satisfaction problem. 
Let's begin with 3 frequently asked 
questions about under-determined 
characteristics of the generic local 
search procedure I just showed you. 
Question number 1 concerns step number 1 
of the algorithm. 
You need to somehow come up with this 
arbitrary starting point, x. 
How do you do it? To answer this 
question, let me crudely classify the 
situations in which you might be using 
local search, into 2 categories. 
In the first category, you're really 
depending on local search, to come up 
with a good approximate solution, to an 
optimization problem. 
You really have no idea how to get close 
to an optimal solution, other than 
through, some local search Approach. 
The second category of scenarios is where 
you have some pretty good heuristics that 
seem to be delivering to you pretty good 
solutions to your optimization problem 
and you just want to use a local search 
as a post-processing step to do even 
better. 
So let's start with the first category 
where all of your eggs are in one basket 
and you need a local search to deliver to 
you a pretty good solution to an 
optimization Problem. 
So this is a tricky spot to find yourself 
in. 
Local search is guaranteed to deliver to 
you a locally optimal solution. 
But in many problems locally optimal 
solutions can be much, much worse than 
what you're looking for, a globally 
optimal solution. 
In the special case of the maximum cut 
problem, we had a performance guarantee 
of 50%. 
Which already is only a so-so guaranteed 
but for most optimization problems even 
that kinds of performance guarantee is 
out of question. 
There are locally optimal solutions far 
worse than the globally optimal ones. 
On the other hand, you know there are 
some good locally optimal solutions out 
there. 
In particular the globally optimal 
solution is also a locally optimal one. 
Now if you just run local search once, 
it's not clear how to evaluate the 
quality of the solution that's returned 
to you. 
You run the algorithm, it hands you a 
solution, it has cost 79,217. 
is that good or bad? Who knows? An 
obvious approach to doing better is to 
run the local search many times, say 
thousands of times, even millions of 
times, and then amongst all of the local 
optima of the different runs of your 
local search algorithm returns, you pick 
the best one and you make that your final 
Final solution. 
To encourage your local search algorithm 
to hand back to you different local 
optima when you run it over and over 
again. 
You want to be making some random 
deicsions. 
An extremely common point to make a 
random decision is in step 1 of local 
search. 
Is in choosing your initial starting 
point .x so, for example in the maximum 
cut problem, you'd want to start with a 
random cut with each vertex equally 
likely to be in a or b. 
With the traveling salesman problem, you 
might want to start from a random tour, 
that is a random permutation of the end 
vertices. 
And if it's a straint satisfaction 
problem you could begin by giving each 
variable Independently a random value. 
If this seems kind of like throwing darts 
at a dartboard, that's what it is. 
It turns out there's a lot of stubbornly 
difficult problems out there for which 
the state of the art is not really 
substantially better than running 
independent trials of local search with 
different random initial positions and 
returning the best of the local optimal 
that you find. 
Now let's suppose you're in this second, 
happier category of scenarios, where 
you've got a better handle on your 
optimization problem. 
Maybe you've figured out how to use 
greedy algorithms, or maybe mathematical 
programming. 
Anyways, you have techniques that 
generate close to optimal solutions to 
some optimization problem. 
But why not make these nearly optimal 
solutions even better? 
How do you do that? We'll feed the output 
of your current suit of heuristics into a 
local search post processing step. 
After all, local search only moves to 
better solutions. It can only make your 
pretty good solution even better.