localsearch

Local search is a class of heuristic optimization techniques that seek high-quality solutions by iteratively improving a current candidate. Starting from an initial solution, the method examines the set of neighboring solutions produced by small modifications to the solution representation, collectively called the neighborhood. If a neighboring solution with a better objective value is found, the algorithm moves to that solution and repeats. The search typically terminates when no improving move is available, or when a predefined limit on time, iterations, or evaluations is reached. Local search does not guarantee a global optimum.

Common strategies include hill climbing, which accepts only improving moves; simulated annealing, which probabilistically accepts worse moves to escape local optima; and tabu search, which imposes short-term memory to avoid cycling. Some approaches combine multiple restarts with perturbations to enhance diversification. In practice, the neighborhood structure and move operators are tailored to the problem to balance solution quality with computational effort.

Applications include combinatorial optimization problems such as the traveling salesman problem, vehicle routing, scheduling, graph coloring, and facility location. Local search is often used as a building block within larger algorithms, including memetic algorithms and other metaheuristics that integrate global search with local refinement.

Limitations and considerations include sensitivity to the representation and neighborhood, potential for getting stuck in local optima or flat regions, and lack of general guarantees of optimality. Performance depends on the quality of the neighborhood and stopping criteria. Despite these limitations, local search can produce high-quality solutions quickly for large instances and is widely used in industry and research.