Back to the on-screen lesson ·
Local search and its relatives, why each escape works by going downhill, and the honest claim a heuristic supports.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to describe local search and a neighbourhood, count the moves in a standard one, and say how simulated annealing, tabu search and their relatives escape a local optimum — all by being willing to accept a worse solution. You will also be able to state exactly what a heuristic run supports as a claim, pair it with a relaxation bound to turn an unbounded answer into a bounded one, and explain why a long plateau is evidence about the search rather than about the problem.
Branch and bound, which is exact and can fail to finish. Relaxations, which give bounds. This lesson is what to do when the exact method will not finish in the time you have — and, more importantly, how to say what you got without overstating it.
Local search. Start from any feasible solution. Define a neighbourhood — the solutions reachable by one small change. Move to a better neighbour. Repeat until no neighbour is better.
For the travelling salesman, the classic neighbourhood is 2-opt: remove two edges from the tour and reconnect the other way, reversing a stretch. With $n$ cities there are about $n^2/2$ such moves against $(n-1)!/2$ tours — the neighbourhood is a vanishingly small sample, which is why the search is fast and why it stops somewhere arbitrary.
Metaheuristics are strategies for escaping the local optimum that local search stops at:
| Strategy | The escape mechanism |
|---|---|
| Simulated annealing | accept a worse neighbour with a probability that falls over the run |
| Tabu search | forbid recently visited solutions so the search cannot fall back |
| Genetic algorithms | keep a population and recombine solutions |
| GRASP | randomised greedy construction, then local search, repeated |
Every one of them works by being willing to go downhill. A method that only ever improves cannot leave a local optimum; that is what "local optimum" means.
What they promise. Every method promises one of three things: a global optimum, a local one, or a feasible answer with a bound on how far from optimal it might be. Reporting the output of a method that promises the third as though it promised the first is the most expensive mistake in this subject, and it is made in words, not in arithmetic.
A heuristic returns a feasible solution. It does not return a bound, it does not certify optimality, and running it longer does not change the kind of claim it supports — only, perhaps, the number. There is no theorem being quoted; there is a search that stopped.
Making it defensible. Pair the heuristic with a relaxation bound. The heuristic gives a value from below (on a maximisation), the relaxation from above, and the difference is a real guarantee. That combination — heuristic for the solution, relaxation for the proof — is how large problems are actually handled.
Another way: picture
A walker in hill country in fog, always stepping to the highest of the few places within reach. They stop on the first hilltop, which may or may not be the highest. Annealing is the walker occasionally agreeing to step downhill early on, in the hope of finding a better hill.
Another way: steps
To use a heuristic responsibly:
Nearest neighbour for a tour: start anywhere, repeatedly go to the nearest unvisited city, return to the start. Fast, simple, and typically 20 to 25 percent worse than optimal.
Greedy for a knapsack: sort by value per unit weight and take items while they fit. Fast, and it can be arbitrarily bad — one item that only just fails to fit can leave most of the capacity empty.
Both illustrate the same point. A greedy rule makes each choice as though it were the last, and the interactions between choices — the thing that made the problem worth modelling in the first place — are exactly what it ignores. That is why construction heuristics are almost always followed by local search, which at least gets to reconsider.
Reporting a heuristic answer as optimal. The mistake this whole course is arranged around. It is made in the write-up, not in the arithmetic.
Running longer to gain confidence. More iterations produce a possibly better solution and exactly the same kind of claim. Confidence is not accumulated this way.
Tuning on one instance. Metaheuristic parameters tuned on a single problem usually do not transfer. Tune across a set, or accept defaults.
Skipping the bound. An LP relaxation is often seconds of work and converts an unbounded answer into a bounded one. It is the cheapest credibility available and it is routinely omitted.
It is evidence about the search: this neighbourhood structure, from these starting points, is not finding anything better. A local search is blind outside its neighbourhood by construction, so a plateau tells you where the method cannot see, not what is there. The confusion is understandable — in branch and bound a plateau really is meaningful, because the bound is meanwhile closing and a plateau there means the proof is nearly finished. That is precisely the difference between the two kinds of method, and it is why the one piece of advice in this lesson worth remembering is: get a bound, however crude, and report it alongside.
A vehicle-routing heuristic returns a plan costing $4{,}820$ after ten minutes.
The output.
Overstated: "The optimal routing costs $4{,}820$." Nothing in the run supports the word.
The claim that was not established.
Honest: "A feasible routing costing $4{,}820$. The LP relaxation bounds any routing below $4{,}510$, so this is within $6.9\%$ of the best possible." Same run, one extra linear program, and a statement that survives being questioned.
The same work, correctly described.
Early in the run the acceptance probability for a worse move is high, so the search moves almost freely and explores widely.
Hot: exploration.
As the temperature falls, worse moves are accepted less often, and the search concentrates on improving what it has.
Cooling: exploitation.
Cool too fast and it behaves like plain local search, stopping at the first hilltop. Cool too slowly and the time runs out while it is still wandering. The schedule is the method's main parameter, and there is no way to choose it from the problem's structure — which is a fair summary of what distinguishes a heuristic from the methods in units 2 and 3.
A parameter with no theory behind it.
A genetic algorithm on a scheduling problem returns a schedule with makespan 47 after 100,000 generations, and the best found has not improved for the last 60,000.
What was actually verified?
Feasibility: yes, the schedule satisfies every constraint. Optimality: not tested. The long plateau is evidence that this neighbourhood structure is not finding anything better, which is not evidence that nothing better exists.
So: "a feasible schedule with makespan 47; no bound computed." To improve the claim, spend a few seconds on the LP relaxation — even a weak bound of, say, 41 turns this into "within 15 percent of optimal", which is a different kind of sentence entirely.
A metaheuristic runs for an hour and returns a feasible plan worth $323$. What may be reported?
A tour visits $5$ cities. A 2-opt move reverses one stretch of the tour, which is picked out by choosing two of its edges. How many such moves are there?
Answer:
A local search has reached a solution with no better neighbour. How does simulated annealing get past it?
A heuristic finds a plan worth $107$ in a maximisation, and the LP relaxation bounds the optimum by $152$. How far from optimal might the plan be?
Answer:
A metaheuristic runs for an hour and returns a feasible plan worth $322$. What may be reported?
A dispatcher needs a good route in under a second, on a problem an exact method cannot finish. What is the right answer?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A tour visits $7$ cities. A 2-opt move reverses one stretch of the tour, which is picked out by choosing two of its edges. How many such moves are there?
Answer:
You can run a local search, name the escape mechanisms, and report a heuristic result without overstating it. That closes unit 4. Next: what to do when there is more than one objective, or the data is not known.
9. Your turn: what claim does this run support?, step 3