Local Search

Local search is a technique that takes as an input a feasible solution to a combinatorial optimization problem, and tries to produce a better solution. The idea, at a high level, is to search locally in a neighborhood of the input point for a solution that immediately improves the objective value. If no such solution can be found, our input is locally optimal and is returned. Otherwise, we recursively call our local search algorithm on the superior point found.

More formally, suppose we are given some optimization problem

where \( S \subset \mathbb R^n \) and \( f \colon S \to \mathbb R \) . In local search, for every \( \mathbf x \in S \) , we must give some \( N_{\mathbf x} \) to be the neighborhood of \( \mathbf x \) . Then given some initial feasible solution \( \mathbf x_0 \) , for \( n = 1,2,\ldots \) , we let

To run a local search algorithm you begin with \( \mathbf x_0 \) , and iterate the above process until it converges, i.e. \( \mathbf x_{n+1} = x_n \) .

The key to making local search work is how we choose \( N_{\mathbf x} \) . We need be able to efficiently optimize over \( N_{\mathbf x} \) , otherwise our local search heuristic will be no easier to solve than our original problem. However, if we define \( N_{\mathbf x} \) to be too small a set, then we may get stuck in a local optimum that isn't very good.

A few warnings about local search:

• Without special problem structure, local search provides no guarentee on the quality of the solution produced relative to the global optimum
• Generally speaking, we do not have a good upper bound on the number of iterations until local search converges. We have the trivial bounds of \( |S| \) , which may be exponentially large, and (if the objective is guaranteed to be integer), \( |f(\mathbf x^*) - f(\mathbf x_0)| \) , which can still often be exponential (assuming the problem has weights which are input in binary).

An example

TODO

Two-Opt for TSP