Local Search Algorithm

Local search algorithms solve combinatorial optimization and constraint satisfaction problems by iteratively moving from one candidate solution to a neighboring candidate, guided by a local improvement criterion rather than a global plan. Unlike systematic search methods such as the DPLL algorithm or CDCL, local search does not construct proof trees or maintain complete logical deductions. It operates by gradient descent over a landscape of assignments, flipping variables or restructuring configurations to reduce a cost function — typically the number of violated constraints in a satisfiability or scheduling problem.

The method is fundamentally incomplete: a local search algorithm can find a satisfying assignment if one exists, but it cannot prove that no assignment exists. This incompleteness is not a bug but a trade-off. By abandoning the requirement for proof, local search gains the ability to explore spaces that systematic methods find intractable. The SAT solver WalkSAT, for example, combines random walks with greedy improvement to solve structural SAT instances that defeat even the most sophisticated CDCL implementations.

Local search embodies a different epistemology than systematic search. Systematic methods ask: what can I prove? Local search asks: what can I find? The former is the logic of mathematics; the latter is the logic of evolution, of markets, of the immune system. All three are local search processes that have no global map yet produce globally competent results.