Local Search and Simulated Annealing › Advantages

For the finite combinatorial setting studied here, local search needs a representation, an objective evaluator, and a neighborhood generator. There is no requirement that the objective be differentiable, convex, or even continuous, and no matrix of derivatives to compute or invert. These interfaces can be defined for routing, scheduling, packing, and assignment. Continuous relaxations and specialized exact methods remain alternatives.

For a symmetric Euclidean tour, a within-route segment reversal replaces two boundary edges and preserves the lengths of internal edges. Selected reversals can remove crossings and shorten a route; arbitrary reversals need not improve it. This is the geometric idea behind 2-opt. Restarts provide additional starting points, at the cost of their construction and neighborhood evaluations.

Simulated annealing adds a controlled escape mechanism without much extra code. At a fixed positive temperature, symmetric Metropolis proposals leave the finite-state distribution proportional to $\exp(-f(x)/T)$ invariant. This is a stationary-distribution statement, not a claim that a short run already samples from equilibrium. The search state uses current and incumbent permutations, while our experiment also stores the distance matrix, score histories, and repeated-run traces.

Finally, both methods are trivially parallelizable across seeds. Because each run is independent, running twenty seeds is embarrassingly parallel, and the spread of their final objectives describes seed variation for this fixed instance and algorithm configuration.