A local optimum of a combinatorial optimization problem is a solution that is optimal (either maximal or minimal) within a neighboring set of solutions. This is in contrast to a global optimum, which is the optimal solution among all possible solutions.
Local search or hill climbing methods for solving discrete optimization problems start from an initial configuration and repeatedly move to an improving neighboring configuration. A trajectory in search space is generated, which maps an initial point to a local optimum, where local search is stuck (no improving neighbors are available). The search space is therefore subdivided into attraction basins, consisting of all initial points which have a given local optimum as final point of the local search trajectory. A local optimum can be isolated (surrounded by non locally-optimal point) or part of a plateau, a locally optimal region with more than one point.
If the problem to be solved has all local optimal points with the same value of the function to be optimized, local search effectively solves the problem: finding a local optimum delivers the globally optimal solution.
In many cases, local optima deliver sub-optimal solutions, and a local search method needs to be modified to continue the search beyond local optimality, see for example iterated local search, tabu search, reactive search optimization, simulated annealing.
See also 
|This applied mathematics-related article is a stub. You can help Wikipedia by expanding it.|