A field guide to making the best decision a model can defend: which plants to open, which route to drive, which schedule to run. From exact methods that come with proofs to metaheuristics and quantum annealing that trade proofs for reach. Every family below has a flagship algorithm implemented from scratch in an open-source companion repo, graded against known optima.
Why any of this matters
Ten wind turbines placed on a sensible engineering grid produce 2.98 MW, because each turbine's wake robs the ones behind it of wind. A particle swarm searching the same site found a staggered layout producing 5.10 MW: 71% more power from identical hardware, within 1.6% of the physical ceiling, purely by rearranging positions. Optimization is the discipline of finding those arrangements on purpose, and of knowing how far from the best possible answer you might still be.
Every optimization problem has the same skeleton: decision variables (what you control), an objective (what you want more or less of), and constraints (what reality permits). The entire zoo of methods is about one question: what structure do these three have (linear, convex, discrete, noisy, black-box), and what can be exploited?
In a convex problem, any local optimum is global, and polynomial-time algorithms exist that terminate with a certificate of optimality. Non-convex landscapes have many basins, and no general method can promise the best one. The first diagnostic question for any new problem: is there convex structure to exploit, or can the problem be reformulated so there is?
Add yes/no decisions to a linear program and it becomes NP-hard. A 30-stop delivery route has more possible tours than atoms in the observable universe; a modest job-shop has ~1033 schedules. Past some scale, proving optimality is hopeless, which is the economic justification for every heuristic on this page.
Exact methods return the answer plus a proof (a bound on money left on the table). Heuristics return an answer and silence. The professional discipline for heuristics: validate the engine on instances with known optima, then grade real runs against provable bounds and honest baselines such as greedy or random-with-equal-budget.
Averaged over all possible problems, every optimizer performs identically. That is a theorem, not a slogan. A method only wins by exploiting structure: linearity, smoothness, decomposability, locality of good moves. The craft is matching method to structure, never defending a favorite hammer.
Declare the algebra (variables, linear or convex objective, constraints) and a solver returns the optimum with a certificate. When your problem fits this box, nothing else on this page should be your first choice.
Linear objective, linear constraints, continuous variables. The simplex method walks vertex to vertex of the feasible polytope, always improving; interior-point methods cut through the middle. Duality yields shadow prices, the marginal value of each constraint, often worth more than the solution itself.
LP plus integer variables for yes/no and how-many decisions. Branch & bound solves LP relaxations, branches on fractional integers, and prunes subtrees whose bound can't beat the incumbent; branch & cut adds cutting planes. NP-hard, yet modern solvers routinely crack thousands of binaries.
Convex quadratic objectives and cone constraints keep the certificate while adding curvature: portfolio variance, least squares with constraints, robust counterparts. Interior-point methods solve them in polynomial time.
Smooth nonlinear objectives or constraints. SQP and interior-point methods converge to local optima; global only under convexity. Good initial points and multistart are part of the method, not an afterthought.
Feasibility-first search with domain propagation: each constraint actively prunes the possible values of its variables. Shines where constraints are rich and logical (precedences, all-different, calendars) and the objective is thin.
When decisions decompose over stages with optimal substructure, solve each subproblem once and reuse it: shortest paths, inventory policies, Held–Karp for TSP. Exact, but the state space explodes exponentially with dimension (the "curse of dimensionality").
Max-flow/min-cut, shortest paths, assignment (Hungarian algorithm), matching, spanning trees: polynomial-time exact algorithms for specific structures. Always check whether your problem is one of these in disguise before reaching for anything heavier.
Between the algebra of exact methods and the population games of metaheuristics sits continuous search: follow the gradient when you have one, model the landscape when you don't.
Step downhill along the negative gradient. With momentum, adaptive step sizes (Adam), and stochastic mini-batches, this is the workhorse of machine learning: cheap per step, scales to billions of parameters, converges to local optima only.
Use curvature, not just slope: Newton's method rescales steps by the Hessian; BFGS/L-BFGS approximate it from gradient history. Far fewer iterations than plain descent on smooth, moderate-dimension problems, and the default for classical statistical fitting.
Nelder–Mead crawls a simplex of points downhill using only function values, with no gradients and few assumptions. Reliable for cheap, low-dimensional, smooth-ish problems; degrades quickly past ~10 dimensions.
When each evaluation costs hours or dollars, spend them wisely: fit a probabilistic surrogate (a Gaussian process) to the evaluations so far and pick the next point by expected improvement, balancing exploring uncertain regions against exploiting promising ones.
Population methods purpose-built for rugged continuous landscapes. CMA-ES adapts a full covariance of its sampling distribution and is the gold standard for hard black-box continuous problems; differential evolution mutates by vector differences and is a robust, nearly tuning-free default.
General-purpose search strategies for problems that are discrete, non-convex, black-box, or all three. No certificates, so the discipline is in the baselines. Two families: trajectory methods perturb one solution; population methods evolve many and share information.
A random walk that always accepts improvements and accepts worsening moves with probability e−ΔE/T, where the temperature T cools over time: roam early, commit late. Simple, robust, and one real design decision: the neighborhood move, where all the domain knowledge lives.
Greedy local search plus memory: recently-made moves become tabu, so the search can't immediately undo them and is forced out of local optima deterministically. Long-term memory adds diversification. Often the strongest single-solution method on scheduling and routing.
Run local search to a dead end, perturb the result, then run again, keeping the better endpoint (ILS). Variable neighborhood search systematically switches between neighborhood structures when one stalls. Deceptively simple; frequently state-of-the-art.
Evolve a population under selection pressure: tournament selection, crossover that recombines building blocks of parents, mutation for diversity, elitism so the best survive. The encoding is where the intelligence lives: a good one makes every genome feasible by construction.
Particles fly through continuous space pulled by inertia, their own best find (memory), and the swarm's best (social attraction). Information spreads instantly, so one particle's discovery redirects the swarm. The result is fast convergence without gradients, and premature convergence as the known failure mode.
Artificial ants build solutions edge by edge, biased by pheromone laid on edges that appeared in good solutions; pheromone evaporates, so bad habits fade. A natural fit for problems whose solutions are paths through a graph.
The pragmatic frontier: metaheuristics that call exact solvers as subroutines, such as large-neighborhood search that destroys part of a solution and re-optimizes it as a MILP, or a GA whose fitness function prices candidates with an LP. Often beats either paradigm alone.
Real inputs like demand, prices, and travel times are forecasts, not facts. Optimizing as if the point forecast were true systematically overfits to it; these frameworks make the uncertainty part of the model.
Optimize expected cost over a tree of scenarios, distinguishing here-and-now decisions (made before uncertainty resolves) from recourse decisions (made after). The value of the stochastic solution measures what point-forecast planning would have cost you.
Optimize against the worst case within an uncertainty set, with no probabilities required. Conservative by design, tractable via convex reformulation, and the right frame when a single bad realization is unacceptable.
Require constraints to hold with probability at least 1−ε: "meet demand 98% of days", "grid stays within limits 99.9% of hours". Sits between expectation and worst case, and maps directly to the service-level language operations already speaks.
A different bet: instead of a cleverer algorithm, a different physical substrate. Encode the problem as energy; let a physical (or simulated-physical) system relax to its ground state.
Annealers accept exactly one input: minimize x'Qx over binary x (equivalently, an Ising spin model). Using them is an exercise in formulation: constraints become quadratic penalties in Q, and penalty weights are real modeling decisions with a classic failure mode: too weak and the "constraint" silently stops binding.
Hardware (D-Wave and kin) prepares qubits in superposition and slowly morphs the system toward the problem Hamiltonian; quantum tunneling can pass through thin energy barriers that thermal methods must climb over. Thousands of physical qubits exist today; limited connectivity and noise mean embedding and formulation dominate practice.
The standard classical simulation of the quantum process: path-integral Monte Carlo runs P coupled replicas of the system whose coupling strengthens as the simulated transverse field anneals away, sampling the same distribution the hardware explores physically. A respectable QUBO heuristic in its own right, and the benchmark quantum hardware has to beat.
QAOA is the gate-model cousin: shallow parameterized quantum circuits tuned by a classical outer loop, still research-stage. Digital annealers (specialized silicon for Ising problems) are quantum-inspired hardware shipping now. The QUBO formulation skills transfer across all of them unchanged.
Two questions sort most real cases. Is there linear or convex structure to exploit? If yes, go exact, because certificates are valuable and modern solvers are fast. If not, what evaluation budget can a search method spend, and what baseline will you grade it against?
| Problem looks like… | Reach for | Certificate? |
|---|---|---|
| Linear, continuous | LP (simplex / interior point) | Yes |
| Linear + yes/no decisions, moderate scale | MILP (branch & bound / cut) | Yes |
| Convex with curvature (risk, squared error) | QP / SOCP (interior point) | Yes |
| Matches a known graph structure | Dedicated algorithm (flow, matching, DP) | Yes |
| Rich logical constraints, scheduling flavor | Constraint programming | Feasibility |
| Smooth nonlinear, local optimum acceptable | NLP (SQP / L-BFGS, multistart) | Local only |
| Discrete, huge, deadline-bound | SA / tabu / GA / ACO + bounds & baselines | No |
| Continuous black-box, cheap evaluations | PSO / differential evolution / CMA-ES | No |
| Continuous black-box, expensive evaluations | Bayesian optimization | No |
| Inputs are forecasts, not facts | Stochastic / robust programming | Model-relative |
| Binary-quadratic; exploring new hardware | QUBO + annealer (or SQA today) | No |
The companion repo, optimization-hub, implements a flagship algorithm from each family from scratch in numpy, with no solver libraries and no black boxes, and grades every one against an independently computed optimum: exhaustive enumeration, exact dynamic programming, or vertex search. Five executed notebooks, each a scaled-down industrial decision:
| Case study | Algorithm | Ground truth | Result |
|---|---|---|---|
| 01. Supply chain (manufacturing) | Simplex + branch & bound | Vertex / subset enumeration | Certified optimum, 4 nodes vs 31 subsets |
| 02. Delivery routing (logistics) | Simulated annealing, 2-opt | Held–Karp exact DP | Exact optimum on 12 stops; −14% vs greedy on 30 |
| 03. Wind-farm layout (energy) | Particle swarm | Benchmark functions + baselines | 2.98 → 5.10 MW vs grid; 1.6% from ceiling |
| 04. Job-shop scheduling (manufacturing) | Genetic algorithm, POX | All 1,680 schedules; lower bound | Exact on 3×3; within 6.5% of bound on 8×5 |
| 05. Portfolio selection (finance) | Simulated quantum annealing | All 216 bitstrings | Ground state found; penalty failure mode shown |
All code, five executed notebooks, the methodology guide, and 15 known-truth tests are open source.
View on GitHub