What do you do when proof is out of reach?
Integer programming (topic 04) is where the corner theorem stops being enough, and branch and bound (05) is the machinery that copes. Topic 19 shares this course's language of variables and constraints but drops the objective: sometimes the honest question is not “what's best” but “does anything work at all.” Topic 21 asks when the simplest rule of thumb is provably good enough, and topic 10 is what you reach for once exact methods die.
Topics 04 and 05 gave you the honest tools: formulate exactly, bound hard, prove optimality. Sometimes that is not available. The model is too large, or the objective is not something you can write as a formula, or you have four minutes and the exact method needs four days.
Then you give up the certificate and keep the answer. A metaheuristic is a strategy for searching a space you cannot reason about exhaustively: simulated annealing, tabu search, genetic algorithms, large-neighbourhood search. They do not prove anything. Used well they routinely return solutions within a percent or two of optimal on problems where the exact method never finishes.
Simulated annealing is the cleanest to understand because it is stolen wholesale from metallurgy. Cool a metal fast and its atoms freeze wherever they happen to be, leaving a brittle mess; cool it slowly and they settle into a low-energy crystal. So: accept improvements always, accept worsening moves with a probability that falls as an artificial "temperature" drops. Hot early to explore, cold late to settle.
The honest boundary, and it is a theorem rather than an opinion: no search method beats any other averaged over all possible landscapes (No Free Lunch, Wolpert & Macready, 1997). Methods win by exploiting structure. Where there is no structure, nothing helps, and a method that looks brilliant is being flattered by the problems it was tested on.
The Metropolis acceptance rule: propose a neighbouring solution, then:
ΔE = E(new) − E(current)
accept if ΔE ≤ 0
otherwise accept with probability exp(−ΔE / T)
At high T almost anything is accepted and the search wanders freely. As T → 0 only improvements survive and it becomes plain hill-climbing. The cooling schedule (how T falls) is the entire design problem.
There is a schedule with a convergence proof. Geman & Geman (1984) showed that cooling as Tk = c / log(k + 2), with c at least the depth of the deepest local basin, converges to the global optimum with probability 1.
And it is useless. Logarithmic cooling is so slow as to be unusable: on the landscapes in this project's own annealing game, where the deepest barrier is 4, that schedule needs roughly 3,000 steps to reach T = 0.5 (twelve times the entire budget) and about 500 million to reach T = 0.2. It converges precisely because it refuses to cool. Every schedule anyone actually uses is geometric, has no proof, and works. That gap between what is provable and what is practical is the honest character of this whole topic.
Simulated annealing is one metaheuristic among several, chosen here because it is playable. The others solve the same basic problem (search a space too large to enumerate, no gradient to follow, no certificate at the end) with a different source of "accept something worse sometimes":
Genetic / evolutionary algorithms keep a whole population of candidate solutions at once instead of one. Encode each as a string (a "chromosome"), score it, and breed the next generation from the fitter half: crossover splices two parents' encodings together, mutation flips a few entries at random so the population doesn't stagnate. Worked example: encode a delivery order as a permutation of 10 stops, breed a population of 50 routes for a few hundred generations, and the population's best converges toward the same answer branch & bound would certify, without ever proving it. Paper: Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press (1975).
Tabu search is plain hill-climbing with a memory. It always takes the best neighbouring move available (including a worsening one, unlike a method that only ever improves) but keeps a short tabu list of recently-used moves it refuses to repeat for a fixed number of iterations, specifically so the search can't just walk straight back to the local optimum it was trying to escape. An aspiration criterion overrides the tabu status when a forbidden move would beat the best solution found so far. Worked example: job-shop scheduling, where the "neighbour" of a schedule is the same schedule with two operations swapped. Paper: Glover, "Tabu Search. Part I," ORSA Journal on Computing 1(3) (1989).
Particle swarm optimisation runs many candidate solutions ("particles") at once through the solution space, each with a position and a velocity. Every particle's velocity is nudged, each step, toward two things: the best position it has personally found, and the best position anyone in the swarm has found, so the population behaves like a flock converging on good territory without any particle knowing the objective's shape in advance. Worked example: minimising a two-dimensional test function, watched live as the swarm visibly contracts onto the minimum over a few dozen iterations. Paper: Kennedy & Eberhart, "Particle Swarm Optimization," Proceedings of IEEE ICNN (1995).
Ant colony optimisation has artificial "ants" construct solutions one step at a time, biased by a pheromone trail left on the graph by earlier ants (more pheromone on an edge means more ants choose it next round) while all pheromone slowly evaporates, so trails that stop being reinforced by good solutions fade out instead of trapping the search forever. Worked example: the travelling-salesman problem, the field's own standard demonstration, where after enough rounds the pheromone map itself becomes a visible picture of the good tour. Paper: Dorigo, Maniezzo & Colorni, "Ant System: Optimization by a Colony of Cooperating Agents," IEEE Transactions on Systems, Man, and Cybernetics 26(1) (1996).
Every algorithm above was actually run against its own worked example, not just described. Verified in Python: the genetic algorithm found the exact brute-force-certified optimum (294.21) on the 10-stop instance by generation 42 of 300; tabu search matched the exact certified-optimal makespan (11) on the 3×3 job-shop instance; particle swarm optimisation collapsed a swarm spread of 13.6 down to 0.06 around the true minimum in 60 iterations, landing on it to four decimal places; and ant colony optimisation found the exact certified-optimal 8-city tour, with pheromone on that tour's own edges settling around 15.8 while every other edge's pheromone evaporated to statistically nothing: the swarm converged so tightly that no ant kept visiting them to refresh the trail. None of this is a proof any of the four scales. These are the honest results of one run against one small, brute-forceable instance, not a general guarantee, but on the instance each paragraph promises, all four did exactly what the paragraph says.
Chip layout, and the delivery van outside Placing millions of components on silicon to minimise wire length is far beyond exact methods, and simulated annealing has been a workhorse there since the 1980s. Vehicle routing at national scale (thousands of stops, time windows, driver rules) is typically solved by large-neighbourhood search: destroy part of a good solution, repair it optimally, keep it if it improved. Nobody proves those routes optimal. They just have to be better than yesterday's, by tomorrow morning.
And the quantum connection Quantum annealing is a physical machine built to imitate exactly this process, using quantum tunnelling instead of thermal hops to cross barriers. Knowing how well the classical version performs is the only way to judge whether the quantum one is beating anything, which is why this topic is the honest baseline for most quantum-optimisation claims.
Check yourself
What does the No Free Lunch theorem say about search methods?
Where there is no structure nothing helps, and a method that looks brilliant is being flattered by the problems it was tested on (Wolpert and Macready, 1997).