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.