Heuristics and Local Search

A local search algorithm operates on a solution space $S$ (all feasible candidate solutions to a problem instance) equipped with a neighborhood function $N: S \to 2^S$, where $N(s)$ is the set of solutions "close to" $s$ under some small, well-defined perturbation — flipping one bit, swapping two elements, reversing a tour segment. Given a cost function $f: S \to \mathbb{R}$ that we want to minimize (or maximize), the algorithm maintains a current solution $s$ and repeatedly tries to replace it with a better neighbor in $N(s)$. A solution $s^*$ is a local optimum with respect to $N$ if $f(s^*) \le f(s')$ for every $s' \in N(s^*)$ — no single move from the neighborhood improves it. This is emphatically not the same as a global optimum, which beats every solution in all of $S$. The gap between the two is the entire subject of this article: local optima can be arbitrarily bad relative to the global optimum, and how bad depends intricately on the choice of $N$. A neighborhood that is "too small" (few candidates to move to) makes search fast but traps you easily; a neighborhood that is "too large" (e.g., all of $S$) makes every step as hard as solving the whole problem again.

Hill climbing (also called steepest descent, iterative improvement, or greedy local search) is the baseline strategy: from the current solution, look at all neighbors, move to the best one that improves on the current cost, and stop when no neighbor improves. It is simple, fast per step, and always makes progress — but it is a strictly greedy rule with no lookahead, so it commits irrevocably to whichever local optimum it first reaches. Metaheuristics are general-purpose strategies layered on top of a basic local search to help it escape local optima: simulated annealing injects randomness governed by a temperature parameter; tabu search forbids revisiting recently seen solutions to force exploration; random restarts simply rerun hill climbing from many different starting points and keep the best result. None of these methods carry a worst-case approximation ratio — this is the price paid for generality, in contrast to the guaranteed-ratio algorithms studied under Coping with NP-Hardness.

Hill climbing is the essential skeleton on which everything else is built. ``` HILL-CLIMB(instance, initial-solution s, neighborhood N, cost f) current ← s repeat best-neighbor ← argmin_{s' in N(current)} f(s') if f(best-neighbor) >= f(current) return current // local optimum reached current ← best-neighbor until false ``` This is first-improvement or best-improvement hill climbing depending on whether we scan `N(current)` for the first improving move or the single best one; both terminate at a local optimum, and both can be led astray by an unlucky neighborhood shape.

Simulated annealing modifies this loop in exactly one way: instead of requiring an improving move, it proposes a random neighbor and accepts it with a probability that depends on how much worse it is and on a temperature $T$ that decreases over the run. Early on (high $T$), almost any move is accepted, so the search wanders broadly and can climb out of shallow basins. Late in the run (low $T$), only improving moves (or negligibly worsening ones) are accepted, so the process settles like hill climbing into whatever basin it currently occupies. ``` SIMULATED-ANNEALING(instance, initial-solution s, neighborhood N, cost f, initial-temp T0, cooling-schedule cool, max-iters) current ← s best ← s T ← T0 for iter ← 1 to max-iters s' ← RANDOM-NEIGHBOR(current, N) Δ ← f(s') − f(current) if Δ < 0 // s' strictly better current ← s' else with probability exp(−Δ / T): current ← s' // accept a worsening move if f(current) < f(best) best ← current T ← cool(T, iter) // e.g. T ← α·T, 0 < α < 1 return best ``` Two design choices govern behavior entirely: 1. The neighborhood $N$. For the Traveling Salesman Problem, a classic choice is 2-opt: pick two edges of the tour, remove them, and reconnect the tour the only other way that keeps it a single cycle (equivalently, reverse a contiguous segment). For graph partitioning, a neighborhood might be "swap one vertex between the two sides." For SAT, it might be "flip one variable's truth value" (this specific case is the basis of the WalkSAT family of heuristics). 2. The cooling schedule. A geometric schedule $T_{k+1} = \alpha T_k$ with $\alpha$ close to but below 1 (e.g., $0.95$–$0.999$) is standard. Cool too fast and the algorithm behaves like plain hill climbing (freezes into the first local optimum found); cool too slow and it wastes time wandering without converging. The figure below shows the core geometric picture: a one-dimensional cost landscape with a shallow local optimum next to a deep global optimum, and the difference between how hill climbing and simulated annealing behave on it.

Per-step cost. For hill climbing, one iteration inspects $|N(s)|$ neighbors and evaluates $f$ on each; if $f$ can be updated incrementally (e.g., a 2-opt move changes tour length by a computable delta rather than recomputing the whole tour), one step costs $O(|N(s)|)$ time. The number of iterations until reaching a local optimum is bounded above by the number of distinct achievable cost values on the improvement path, which in the worst case can be exponential in the instance size — there exist crafted instances (e.g., certain "PLS-complete" problems, formalized in the complexity class Polynomial Local Search) where any sequence of improving moves under a natural neighborhood takes exponentially many steps to reach a local optimum. In practice, though, hill climbing on structured instances (TSP with 2-opt, graph coloring, MAX-SAT) tends to converge in a low-degree polynomial number of steps.

Simulated annealing complexity. One iteration is $O(|N(s)|)$ or $O(1)$ if only a single random neighbor is sampled (the usual implementation). Total running time is $O(\text{max-iters})$ evaluated moves — a parameter you choose, not a function of instance difficulty, which is exactly the point: you trade guaranteed quality for bounded, controllable runtime.

No worst-case approximation guarantee — and why this is unavoidable. For an arbitrary NP-hard optimization problem with an arbitrary neighborhood, one can construct instances where every local optimum is arbitrarily far from the global optimum. Consider MAX-CUT with the "flip one vertex" neighborhood: it is known that local optima under this neighborhood can be a factor of $2$ worse than the global maximum in the worst case, and richer problems admit far worse gaps under natural neighborhoods. This is not a defect of a particular heuristic; it is a statement about the neighborhood structure itself, and it explains why local search papers report empirical performance rather than proved ratios — contrast this with the certificate-carrying guarantee proved in A 2-Approximation for Vertex Cover.

When is a local optimum provably global? This is the positive side of the theory, and it is worth stating precisely, because it explains why local search works so well on some problems and fails on others. Claim. If the cost function $f$ is convex over a convex solution space $S \subseteq \mathbb{R}^n$, and the neighborhood $N(s)$ contains all points within any sufficiently small ball around $s$ (a "local" neighborhood in the calculus sense), then every local minimum is a global minimum. Proof sketch. Suppose $s^*$ is a local minimum but not global, so there exists $s^{\dagger}$ with $f(s^{\dagger}) < f(s^*)$. Consider the segment $s(t) = (1-t)s^* + t\,s^{\dagger}$ for $t \in [0,1]$, which lies in $S$ by convexity. Convexity of $f$ gives

For $t$ small enough, $s(t)$ lies in any neighborhood of $s^*$ that includes a small ball, so $s^*$ has a neighbor of strictly lower cost — contradicting local optimality. $\blacksquare$ This is exactly the fact that makes gradient descent reliable on convex functions and explains the special role of matroid structures and other combinatorial analogues of convexity (e.g., local search on a matroid's independent sets with an exchange neighborhood provably finds the global optimum for linear objectives — the theoretical backbone of the Greedy Algorithms and Matroids family of results). The moment $f$ or $S$ loses this convex-like structure — as almost every interesting NP-hard combinatorial problem does — the guarantee evaporates, and we are left with heuristics.

Why simulated annealing "should" work (informally). Model the search as a Markov chain over $S$ where the transition probability from $s$ to a proposed neighbor $s'$ is $\min(1, e^{-(f(s')-f(s))/T})$. At fixed temperature $T > 0$, this chain is a Metropolis–Hastings chain whose stationary distribution is the Boltzmann distribution

As $T \to 0$, $\pi_T$ concentrates all its probability mass on the global minima of $f$. This gives the theoretical justification for annealing: if $T$ is decreased slowly enough (a logarithmic schedule $T_k = c / \log(k+2)$ suffices under classical results on Markov chain mixing), the process converges in probability to a global optimum as the number of steps grows. This is a genuine asymptotic guarantee — but the required schedule is so slow that it is impractical, which is exactly why every real implementation uses a much faster geometric cooling schedule that sacrifices the asymptotic guarantee for a usable running time. The theory tells you why annealing has a chance of working; the practice reminds you that the "correct" schedule is too slow to use.

Consider a tiny Traveling Salesman Problem instance with five cities placed as coordinates, and the 2-opt neighborhood (reverse a segment of the tour). Distances are Euclidean, rounded to one decimal.

Start with the arbitrary tour $A \to B \to D \to C \to E \to A$.

Step 1 — evaluate the initial tour.

Step 2 — hill climbing with 2-opt. Try reversing the segment between B and C (edges A–B and D–C removed, replaced by A–D and B–C), giving tour $A \to D \to B \to C \to E \to A$:

This is an improvement ($22.47 < 23.57$); hill climbing accepts it. From here, checking all remaining 2-opt moves on this new tour reveals no further strict improvement — for instance reversing B–C to test $A \to D \to C \to B \to E \to A$ gives edges $A$–$D=5.00$, $D$–$C=5.00$, $C$–$B=4.00$, $B$–$E=3.16$, $E$–$A=2.83$, total $20.99$ — actually better. So hill climbing continues, accepts this move, reaching total $20.99$.

Step 3 — genuine local optimum. Suppose after exhausting all 2-opt moves from $A \to D \to C \to B \to E \to A$, no reversal improves the total (this is the case here, since the tour visits the four "outer" cities B, C, D in an order consistent with their convex-hull positions and threads E in the only improving slot). Hill climbing halts, returning tour length 20.99. For this small instance, exhaustive checking confirms this is in fact the global optimum — but the point of this example is not that hill climbing always finds it; it is that hill climbing stops as soon as it can't improve, whether or not that point is global.

Step 4 — where simulated annealing differs. Suppose the initial tour had instead been trapped at a different local optimum, such as $A \to C \to B \to D \to E \to A$ with total length 26.1 (worse), and every single 2-opt reversal from that tour happens to increase cost (a plausible configuration on slightly perturbed coordinates). Plain hill climbing would halt at 26.1 forever. Simulated annealing, at moderate temperature, would sometimes accept a worsening 2-opt move — say one that raises cost by $\Delta = 1.2$ — with probability $e^{-1.2/T}$. At $T = 2$, this acceptance probability is $e^{-0.6} \approx 0.55$, so roughly half the time the search escapes this configuration into a different basin, from which it may find the deeper 20.99 optimum. As $T$ cools toward 0 over subsequent iterations, such escapes become rare and the search settles — ideally into the better basin it has by then discovered. This is the entire qualitative story of the method: identical neighborhood, identical cost function, but a controlled willingness to accept short-term losses in exchange for long-term gains — a willingness that shrinks over time.

Local search and simulated annealing sit at the intersection of statistical physics, operations research, and theoretical computer science. The key conceptual leap — using a physical analogy (slow cooling of metal, "annealing," which allows atoms to settle into a low-energy crystal lattice rather than a defect-ridden glassy state) to design a general optimization algorithm — came from a 1983 paper by Kirkpatrick, Gelatt, and Vecchi, building directly on a 1953 Monte Carlo sampling algorithm due to Nicholas Metropolis and collaborators.

Local search and its metaheuristic descendants are the workhorses of applied combinatorial optimization precisely because so few real problems have clean polynomial-time exact algorithms or tight approximation guarantees. Chip placement and routing in VLSI design uses simulated-annealing-style local search to minimize wire length and congestion across billions of components. Airline crew scheduling and vehicle routing systems use large-neighborhood local search (often called "large neighborhood search" or LNS) to handle scheduling constraints that defy clean combinatorial structure. Modern SAT solvers include local-search components (WalkSAT and its descendants) as a complement to systematic backtracking search, especially effective on randomly generated or loosely constrained instances. Training neural networks is, at its core, local search over a continuous, extremely non-convex landscape — stochastic gradient descent with momentum and learning-rate schedules is a close cousin of simulated annealing, trading a decaying "temperature" (learning rate) for the ability to escape shallow local minima in loss landscapes. Protein structure prediction, hyperparameter tuning, and job-shop scheduling all lean on the same family of ideas. As you move next into Online Algorithms and Competitive Analysis, you will meet a different response to the same underlying tension — problems where you cannot even see the whole input in advance — but the guiding lesson from local search persists: when no algorithm can certify optimality, the right question shifts from "can I prove this is good?" to "how do I systematically search for good, and how do I know empirically when to stop?"

Ask the tutor: Why does a slow logarithmic cooling schedule guarantee convergence to the global optimum in simulated annealing, while the geometric schedules used in practice do not?