JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Local Search and Metaheuristics

When a problem is NP-hard and no clean approximation factor is in reach, you can still do something that works astonishingly well in practice: start with any solution and keep nudging it toward something better. This guide builds local search from the ground up, shows exactly why it gets stuck, and explains the metaheuristics that climb back out.

When proofs run out, you still need an answer

By this point in the ladder you have collected a powerful toolkit, and also a sobering map of its edges. Some problems are NP-complete, so no polynomial algorithm is known. Approximation gives you a worst-case factor for some of them — the metric-TSP 2-approximation is a model citizen — but for many problems even a good approximation ratio is hard to come by, or the constant it promises is too loose to be useful. Yet a working engineer cannot reply 'this is NP-hard, so I give up.' A delivery route still has to be drawn this morning. Local search is the honest, pragmatic answer to that gap.

The idea is almost childishly simple, and that is its charm. Forget about searching the whole astronomically large space of configurations at once. Instead, hold one candidate solution in your hand. Define a notion of which solutions are neighbors of it — small, local changes you are allowed to make. Look around at the neighbors, and if any of them is better by your cost measure, step to it. Repeat. You are walking across a landscape of solutions, always downhill (for a minimization problem), one small step at a time, until no neighbor improves on where you stand.

Two design decisions define a local search, and everything else follows from them. First, the neighborhood: given a solution, which others count as one step away? For the Traveling Salesman Problem the classic answer is 2-opt — a neighbor is any tour you get by cutting two edges of the current tour and reconnecting the two paths the other way. For Boolean satisfiability a neighbor is the assignment you get by flipping one variable. Second, the objective: a number you are trying to push down (tour length, number of unsatisfied clauses). Choose those two well and you have an algorithm; choose them poorly and you have a very fast way to find mediocre answers.

The landscape, and why it traps you

Picture every possible solution as a point on a vast terrain, with its objective value plotted as height. Local search is a hiker who can only see one step in every direction and always walks downhill. The destination it can actually reach has a precise name: a local optimum — a solution none of whose neighbors is better. The trouble is the word local. A local optimum is the bottom of some valley, but the terrain may hold many valleys of wildly different depths, and our short-sighted hiker has no way of knowing whether it has found the deepest one (the true global optimum) or merely a shallow dimple.

This is the same crack you first met when you learned that greedy reasoning can mislead. Greedy fails precisely because 'looks locally best' is not a proof of global optimality, and the gap between local and global optima is exactly that failure dressed in geometric clothes. Plain local search — often called hill climbing (or, downhill, gradient descent's discrete cousin) — has no defense against it. The moment every neighbor is worse, it halts. It is honest about stopping, but it cannot promise the stop is anywhere near the best.

Climbing back out: the metaheuristic toolbox

If pure downhill walking gets stuck in the first valley, the obvious fix is to occasionally allow an uphill step so the hiker can climb out of a shallow valley and search for a deeper one. A metaheuristic is exactly that: a general, problem-independent strategy wrapped around local search that decides when and how to escape local optima. The umbrella term metaheuristics and local search covers a whole family of these escape strategies, and they share a recognizable shape — explore aggressively at first, then settle down.

The cleanest member of the family is simulated annealing, borrowed from how a slowly cooled metal settles into a low-energy crystal. At each step you propose a random neighbor. If it is better, you always accept it. If it is worse by an amount d, you still accept it with probability exp(-d / T), where T is a 'temperature' you lower over time. When T is high, almost any uphill move is accepted, so the search roams freely and pops out of shallow valleys. As T cools toward zero, uphill moves become vanishingly unlikely and the method hardens into ordinary hill climbing, polishing whatever deep valley it has wandered into.

s = random initial solution
for T = T_hot down to ~0 (cooling schedule):
    s' = a random neighbor of s
    d  = cost(s') - cost(s)
    if d < 0:            s = s'           # better: always move
    else with prob exp(-d / T): s = s'    # worse: sometimes move
return best s ever seen
Simulated annealing: accept improvements always, accept worsenings with a probability that shrinks as the temperature T cools.

Other members swap one part of the recipe. Tabu search keeps a short memory of recently visited solutions and forbids returning to them, which stops the hiker from immediately walking back down into the valley it just escaped. Genetic algorithms keep a whole population of solutions and 'breed' new ones by recombining pieces of good parents, mutating occasionally — local search done in parallel with crossover. They differ in machinery but share the soul: a local move set, an objective to push down, and a controlled willingness to go the wrong way temporarily in order to go further right eventually.

A worked picture: WalkSAT on satisfiability

Let us make this concrete on the most fundamental NP-complete problem of all, Boolean satisfiability. We have a formula in conjunctive normal form — a big AND of clauses, each clause an OR of a few literals — and we want a true/false assignment to the variables that makes every clause true. The objective for local search is the number of unsatisfied clauses; we want to drive it to zero. A neighbor of an assignment is the same assignment with exactly one variable flipped. The terrain has 2^n points (one per assignment), so enumerating is hopeless, but each point has only n neighbors.

  1. Start from a random assignment of all n variables to true or false. Count the unsatisfied clauses.
  2. If every clause is satisfied, you are done — output the assignment. This is the global optimum (objective 0); there is nowhere lower to go.
  3. Otherwise pick an unsatisfied clause at random. Every variable in it, if flipped, would make that clause true — so a flip here makes local progress.
  4. With some probability flip the variable in that clause that breaks the fewest other clauses (the greedy, downhill move); otherwise flip a random variable from the clause (the noisy, possibly-uphill move that lets you escape traps). This blend of greed and noise is the heart of WalkSAT.
  5. Loop back to step 2, up to some budget of flips. If the budget runs out, restart from a fresh random assignment.

Notice what the noise buys you. Pure greedy flipping — always reduce the unsatisfied count — would jam in the first local optimum, an assignment where every single flip makes things worse even though some clauses remain unsatisfied. The random-flip option is the simulated-annealing 'accept a worse move' trick in disguise: it occasionally raises the objective so the search can leave a trap. In practice this combination solves enormous satisfiability instances that no exact method could touch, which is why solvers built on these ideas quietly power chip verification and scheduling tools today.

The honest fine print

Now the cautions, because this is exactly where local search is most often oversold. The biggest one: a metaheuristic almost never comes with a proof. Simulated annealing has a famous theorem that with an infinitely slow cooling schedule it converges to the global optimum — but 'infinitely slow' means slower than brute force, so the theorem is a reassurance, not a usable guarantee. With any practical schedule you get no bound on solution quality and no bound on running time. This is the opposite end of the spectrum from a guaranteed 2-approximation you trust to be within a factor of 2 on every input.

So why trust a method with no guarantee? Because the worst case and the typical case can be worlds apart, and local search lives off that gap. This is the same lesson the next guide makes precise with smoothed analysis: an algorithm can be theoretically awful on adversarial inputs yet excellent on the inputs that actually arise. The simplex method for linear programming is the famous case — exponential in the worst case, lightning-fast in practice — and local search heuristics share that personality. Their warrant is empirical: they are tuned and tested on real instances, and they earn their keep by results, not theorems.

Step back and see where this sits in the ladder. The earlier rungs gave you algorithms you could prove: a correct invariant, a tight asymptotic bound, a guaranteed approximation factor. This rung's frontier methods trade some of that certainty for reach. Local search is the most pragmatic of the lot — it abandons worst-case guarantees almost entirely and asks only 'does it work on the instances I actually face?' That is not a retreat from rigor; it is rigor about a different question. Knowing when a provable method is within reach and when to drop down to a well-engineered heuristic is itself a mark of mastery.