# Local search

The local search is a generic term for a number of metaheuristic search techniques of combinatorial optimization . The methods are used in many variations to approximately solve complicated optimization problems (e.g. the traveling salesman problem ). The basic principle is to find a better solution based on a given starting solution by finding a better solution from the neighborhood under consideration by locally changing the current solution.

## Formal definition

An instance of a combinatorial optimization problem is a pair in which the set denotes the set of all possible solutions and the function assigns a cost value to each solution. The aim of optimization is (in the case of a minimization problem) to find a solution so that applies to all . The local search works as follows: ${\ displaystyle (L, f)}$${\ displaystyle L}$${\ displaystyle f \ colon L \ rightarrow \ mathbb {R}}$${\ displaystyle i \ in L}$${\ displaystyle f (i) \ leq f (u)}$${\ displaystyle u \ in L}$

1. Determine a starting solution .${\ displaystyle i \ in L}$
2. Define a neighborhood of too "similar" solutions.${\ displaystyle i}$
3. Search this neighborhood or part of it and determine the best solution.

The exact type of local search is determined by how a starting solution is generated (e.g. randomly generated or by a construction heuristic), how the concept of neighborhood is defined and how the termination conditions are set. These definitions are usually problem-specific. Some examples of neighborhood functions are given below:

• With the K-Opt heuristics for the problem of the traveling salesman , two solutions (in this case round trips) are adjacent if the other tour can be constructed by removing edges and adding other edges in one tour.${\ displaystyle k}$ ${\ displaystyle k}$
• In the case of integer linear programs , two solutions can be adjacent if a certain set of variables in both solutions has the same value. A possible local search strategy here is to fix these variables on the common value and to solve the rest of the problem exactly.

## literature

• Local Search in Combinatorial Optimization, Emile Aarts and Jan Karel Lenstra, John Wiley & Sons, 1997, ISBN 0471948225

## Individual evidence

1. Juraj Hromkovic, Theoretical Computer Science : p. 279