Anatomy of a Failed Anneal
201 committed runs. Nine hours of compute. Not one feasible answer. This takes the failure apart, isolates its three causes, and reaches a few percent of the proven optimum in milliseconds — in your browser.
Understand exactly what you're looking at
The theory, how the data is acquired and cleaned, how to read the result — and what BIS would do for you next.
Simulated annealing accepts an uphill move with probability exp(−Δ/T): at high temperature it wanders freely, and as T cools it settles toward good states. On a 0/1 knapsack that schedule is the entire mechanism — get it wrong and you have a random walk in an annealer’s clothes.
Because the instance here is small and fixed, its exact optimum is computed by a dynamic program in milliseconds. Every claim on the page is checkable against a proven number rather than against another heuristic.
A public repository holds three CSV files under results/ — 201 runs of a simulated annealer on a knapsack, every row marked infeasible, together costing 8.94 hours of compute. That is the fixture summarised on the page.
The demo itself does not replay those runs — the original generated a fresh unseeded catalogue each time, so the exact instances are unrecoverable (a small lesson about publishing results). Instead it runs the same annealer live on a fixed, seeded instance so the behaviour is reproducible.
Three defects, all visible in the source, explain every one of those infeasible rows:
- The temperature never means anything. Runs start at 4×10⁵ to 1.02×10⁹ against an objective in the hundreds, so
exp(−Δ/T)is indistinguishable from 1 — every uphill move accepted, at every temperature. The cooling schedule is decoration. - The penalty pays you to overfill. An infeasible solution is charged a constant Big-M, so once you are over capacity the charge stops growing while adding items keeps improving the objective. It ends up loaded to ~15× capacity.
- There is no incumbent. The class returns wherever the walk stopped; it never keeps the best solution it has seen. Thousands of good states are visited and thrown away.
(As committed it no longer even runs — it uses np.float and np.float128. The fix is three lines; the diagnosis is the whole skill.)
Watch the acceptance rate: pinned at 100% is the tell that temperature was never in the loop. The chart separates where the walk is from the best seen so far — the gap between them is exactly the incumbent the original threw away.
Against the dynamic program’s proven optimum, a correctly-scaled anneal that keeps its incumbent lands within a few percent almost immediately — the same method that produced 201 failures, once the three defects are removed.
Anyone can run a metaheuristic until it prints a number. Reading the acceptance rate, noticing it is pinned at 100%, and recognising the schedule was never engaged — that is the part worth hiring.
BIS is who you call when an optimizer “works” but the results are quietly wrong: we instrument it, isolate the cause against a proven baseline, and tell you honestly when a heuristic should be replaced by an exact method.
This preview runs on real public data. Yours would run on your data.
We start with a conversation, prove the value on a focused POC with your real data, then ship it — in our environment or deployed into yours.