Your overnight run must return a plan by morning: how do you choose between a deadline-stopped exact search and a local-search heuristic?
answer
- both return a plan
- only one returns a claim
- ask who defends the number
- seed the exact run first
- label it, never assume optimal
basics
~20 sDecide by what has to be defended. A deadline-stopped exact search returns a plan plus a proven interval containing the optimum; a local-search heuristic returns a plan and no claim at all. Where nobody needs the certificate, the heuristic scales further.
solid answer
~50 sBoth return a feasible plan by morning, so the difference is the **claim attached to it**. A stopped branch-and-bound run holds its incumbent *and* the best bound over unexplored nodes, so you can state that the optimum lies in that interval — a certificate someone can sign off. Local search, including annealing-style methods, returns whatever it found, with no statement about distance from optimal. Ask what the number is for: a contract, an audit or a negotiation needs the interval; an internal plan usually does not. Then take the hybrid — run the heuristic first, seed the exact search with its result so pruning starts at once, and let the exact run improve it and certify what it can. Whatever ships, label it honestly: *best found*, with the gap if you have one, never *optimal* by default.
go deeper
Remember the distinction: some methods can say how close to the best possible answer they are, and others only return the best thing they happened to find. Never describe the second as optimal.
Explain what each method holds at a deadline — an incumbent plus a remaining bound versus a plan alone — and why a local optimum is not evidence about the global one.
Show the operational build: seed the exact search from a heuristic, record the gap, the budget and the seed every night, and watch the gap trend as the signal that the instance family has moved.
Own the tradeoff itself. Decide whether anyone has to defend the number, whether the modelled objective deserves exact treatment, and what evidence would make you switch methods rather than tune the current one.
## Both finish by morning; only one makes a claim The deadline is fixed and both approaches respect it, so the choice is not about speed. It is about what each has in hand at 06:00. | | Deadline-stopped exact search | Local-search heuristic | |---|---|---| | Returns | a feasible plan | a feasible plan | | Optimality statement | optimum lies in a proven interval | none | | Behaves well when | the instance is within reach | the instance is far past exact reach | | Runtime predictability | erratic; the gap varies by instance | steady; you choose the effort | | Failure mode | a wide, useless interval | a good plan nobody can price | A stopped exact search holds two numbers: its **incumbent** cost, and the smallest bound among the nodes it never opened. The optimum sits between them, so the difference is a proven ceiling on what is still being left on the table. Local search holds one number, the cost of what it found, and can add nothing about how far that is from the best possible. A local-search run that stops improving has reached a point where its moves find nothing better — a *local* optimum — which says nothing about the global one. ## The question behind the question What is the number for? - **Someone must defend it.** A tender, a regulated plan, a negotiation over how much a constraint is costing — all need the interval. Here the exact search earns its cost, and a wide-but-honest gap is still worth more than a confident plan with no evidence. - **Nobody will ever ask.** Tonight's routing goes out and is superseded tomorrow. Then the certificate is unused work, and the effort belongs in a better plan rather than a provable one. - **Feasibility itself is in doubt.** If it is genuinely unclear whether any valid plan exists, a heuristic that fails to find one has proven nothing. An exact method can return *infeasible* as a real answer. - **The objective is a proxy.** If the modelled cost only approximates what the business cares about, an exact optimum of the proxy is precision about the wrong thing, and the certificate is false comfort. Say so rather than buying it. ## The hybrid is usually right The two are not exclusive, and the mature answer combines them: 1. Run a fast heuristic first, for a fraction of the window. 2. Seed the exact search's incumbent with its result, so pruning bites from the root instead of after a full descent. 3. Let the exact search improve the incumbent and narrow the interval for as long as the window allows. 4. At the deadline, report the best plan and whatever interval was proved — sometimes zero, sometimes wide, sometimes unknown. The seeded start is the cheap part and it changes the exact run's whole trajectory, because a bound comparison against an infinite incumbent prunes nothing at all. ## Honest labelling is a design requirement The failure this material really guards against is not choosing wrong. It is shipping a plan whose provenance is lost by the time it reaches a decision. - Emit the label with the plan: **proved optimal**, **best found, within X of optimal**, or **best found, gap unknown**. Never let the third silently render as the first. - Record the wall-clock budget spent, since tomorrow's wider gap may mean a harder instance rather than a regression. - Randomised methods need their seed recorded, or last night's plan cannot be reproduced when someone questions it. - A heuristic result that happens to be optimal is still uncertified. Unproven is not the same as wrong, and *cannot prove* is not *is worse*. ## What makes the decision flip - **Scale.** Past the size where the exact search proves anything useful, the interval degenerates to *between this plan and almost nothing*, and the certificate stops carrying information. - **Nightly predictability.** Exact solve times swing hard between similar instances. A pipeline that must hand over at a fixed time may prefer the heuristic's steady cost and spend the saved variance elsewhere. - **Instance drift.** A method chosen when instances were small quietly becomes the wrong one as they grow. The gap over time is the signal, which is why it belongs in the nightly record rather than in someone's memory. The defensible position is not a preference between the two. It is being able to say which one ran, what claim it supports, and what would make you switch.
- What does running a fast heuristic before the exact search buy the exact search?A starting incumbent. Bound-based pruning compares candidate subtrees against the best plan found so far, and with none the first descent prunes nothing. A seeded incumbent makes cuts possible from the root, so the exact run spends its window improving and certifying rather than finding a first feasible plan.
- The gap reported by the nightly run has widened over several months. What does that tell you?Usually that the instances have grown or hardened, not that the code regressed. The exact search now proves less inside the same window. It is the signal to re-examine the choice: seed better, widen the window, tighten the model, or accept that the instance family has moved past what an exact method can certify.
- A local-search run stops improving well before the deadline. Is it finished?It has reached a point where its move set finds nothing better, which is a local optimum, not a proven global one. The remaining time is better spent escaping it: perturb and restart, widen the neighbourhood, or accept worsening moves temporarily. Stopping and reporting the plan as best possible is the error to avoid.
saying these in an interview costs you the question
- Reporting a heuristic's plan as optimal because nothing better was found
- Treating a stopped exact run's incumbent as proven without its bound
- Assuming a heuristic that stops improving has reached the global optimum
- Buying an exact certificate over an objective that only proxies the real one
- Failing to record the seed of a randomised run, making last night irreproducible
- Choosing once and never revisiting as instances grow