Local Search and Simulated Annealing

Many of the optimization problems we care about do not have a differentiable objective we can hand to a gradient method. A delivery planner wants to order eight stops into two delivery routes; a compiler wants to schedule instructions to minimize register pressure; a logistics team wants to re-sequence a pick list to shave a few kilometers off the day. In each case the decision variable is a discrete arrangement (a permutation, a schedule, a subset), and the objective is defined on that arrangement. Gradient descent cannot move "a little bit" in a discrete space, so we need a different strategy: propose a small structural change, evaluate the result, and keep it if it helps.

Local search applies that idea to a chosen neighborhood. We start from some feasible solution, examine a curated set of nearby solutions obtained by a small edit called a neighborhood move, and step to a better one. If we only ever accept improvements, the procedure is called hill climbing (or descent, when minimizing). Its strict-improvement rule is easy to trace on a small routing example. Its weakness is that it can get trapped: it stops improving even though some distant solution is far better.

Simulated annealing addresses that trap by occasionally accepting a worse solution, with a probability that shrinks over time as a virtual "temperature" cools. The name draws on physical annealing: temperature controls thermal motion, and cooling affects how a material settles into lower-energy states. In optimization, the random uphill moves early on give the search a chance to escape a basin, and the gradual cooling lets it settle back down at the end.

In this chapter we build both algorithms from primitives on a concrete eight-customer routing instance, watch them in action, and compare them, under an equal evaluation budget and across twenty random seeds, against a deterministic construction heuristic and a random baseline. The instance is new and deliberately small so that we can enumerate every one of the 40,320 permutations and know the true optimum. That reference lets us measure the distance from each reported objective to the enumerated minimum. Reference enumeration, figure diagnostics, and post-run validation are outside the search budgets. Every method also builds the same nearest-neighbor start using 36 candidate-arc lookups; its complete objective score counts as evaluation one.