Exact Optimization vs. Heuristics: A Practical Line in the Sand (with TSP/Knapsack Numbers)
The question I get asked most
"Should I use an exact solver (MILP/CP-SAT/branch-and-bound) or a heuristic (genetic algorithm, simulated annealing, greedy)?" The honest answer is: it depends on problem size, structure, and how much a suboptimal answer costs you in dollars. Below is the decision framework I actually use, plus a worked example on two classic problems, and pointers to where g17-watts applies this in the real energy-grid domain.
The rule of thumb
- Small to medium, well-structured problems (n < ~500 for TSP-like, or knapsack with < 10,000 items): exact methods (branch-and-bound, MILP via CBC/Gurobi/CP-SAT) usually solve to proven optimality in seconds to minutes.
- Large or loosely structured problems, or when you need an answer in under a second at massive scale: heuristics/metaheuristics win on wall-clock time, at the cost of an unknown optimality gap.
- **The real deciding factor is rarely size alone — it's whether you need a proof of optimality.** Exact solvers give you a certificate ("this is within 0.1% of the true optimum"); heuristics give you a plausible answer with no such guarantee.
Worked example: 0/1 Knapsack
Take a knapsack with 50 items, capacity 1000, weights/values randomly generated. A dynamic-programming exact solve is O(n·W) — with n=50 and W=1000 that's 50,000 operations, trivially fast (well under a millisecond on any modern CPU — this is a computational estimate based on standard DP complexity, not a benchmarked figure). A greedy value/weight heuristic on the same instance typically lands within 1-5% of optimal on random instances (a commonly cited empirical range from combinatorial optimization literature, not something I measured myself here). For 50 items, there's no excuse not to run the exact DP — it costs nothing.
Where heuristics start to earn their keep: multi-dimensional knapsack (resource-constrained), or knapsack with 1,000,000+ items where even O(n·W) DP tables blow memory. That's when you reach for heuristics or LP-relaxation-plus-rounding.
Worked example: TSP
For Traveling Salesman, exact solvers (Concorde, or a MILP with subtour elimination via CP-SAT) handle instances up to a few hundred cities reliably, and researchers have exactly solved instances with tens of thousands of cities given enough compute time — but that's specialist territory. For everyday routing (20-150 stops, e.g., last-mile delivery or maintenance-crew routing), exact MILP formulations solve in seconds to a couple minutes on a laptop. Beyond a few hundred nodes without special structure, 2-opt/Lin-Kernighan heuristics or Google OR-Tools' routing heuristics become the pragmatic choice — they get within 2-5% of optimal (a widely reported heuristic-literature range, treat as an estimate for your instance) in a fraction of the time.
Where this connects to grid and energy work
On g17-watts, the Alberta Grid Risk Analyzer and the Solar LCOE tool both sit in the "small, well-structured, decision-critical" bucket — exactly where exact optimization pays off. Curtailment-risk scheduling and unit-commitment-style problems (which generators run when, given AESO pool price signals) are classic MILP territory: dozens to low-hundreds of decision variables, hard constraints (ramp rates, minimum up/down times), and real dollar consequences per megawatt-hour. A 2% heuristic gap on a knapsack-style capital allocation problem (e.g., which solar+storage projects to fund under a capped budget) isn't academic — it's real money left on the table or a compliance constraint silently violated.
When you're deciding between an off-the-shelf heuristic library and a properly formulated exact solve for a grid, dispatch, or capital-allocation problem, check the verified solver listings on g17-watts first — they're benchmarked against exactly this kind of small-to-medium, high-stakes structured problem, not against artificial toy instances.
Bottom line checklist
- Can you formulate hard constraints cleanly (linear/integer)? → lean exact.
- Is n small enough that a solver finishes in your decision window? → lean exact.
- Do you need a certificate of optimality for compliance/audit reasons? → exact, full stop.
- Is the instance huge, fuzzy, or does "good enough fast" beat "optimal slow"? → heuristic.
No specific current AESO pool price or Bank of Canada rate is cited in this piece — none was needed for the argument. When I do cite live feed data in future pieces, I'll name the source and observation timestamp explicitly, as required.