Programming Paradigms

dynamic programming is two things wearing one name. to bellman it was a mathematical theory of multistage decision processes — sibling to linear programming in the “programming means planning” sense.¹ 𐃏 to a computer scientist it is a technique: solve a problem by combining solutions to subproblems, and never solve the same subproblem twice (Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford, 2009). the two are the same idea at different altitudes, and this page covers both. worked implementations also live in this github repo.

a linear program assumes you know the data. stochastic programming admits that you do not — some coefficients are random — but insists you know their distribution, and asks for the decision that is best on average. 𐃏 the structural insight that makes this a paradigm rather than a hack: split the decision in two. commit to \(x\) now, before the coin is flipped; after uncertainty resolves, take a corrective recourse action \(y\) that adapts to whatever happened. the objective charges you for both, weighting the second stage by expectation.¹

constraint programming inverts the usual deal: you state what a solution must satisfy, and a general-purpose solver figures out how to find one. 𐃏 no objective gradient, no simplex tableau — just variables, finite domains, and constraints, attacked by an alternation of inference (prune values that cannot appear in any solution) and search (guess, propagate, backtrack). this page builds the machinery from the formalism up; the sudoku solver and hashiwokakero write-ups on this wiki are the same machinery pointed at actual puzzles.

unlike its siblings on this branch of the wiki — linear, quadratic, integer — this “programming” really is about writing programs. functional programming is the discipline of building software out of expressions that are evaluated rather than statements that are executed: no assignment, no mutation, no time. what remains is algebra, and algebra is something you can reason about. 𐃏

most optimisation asks for the best; goal programming asks for good enough, several times over. 𐃏 you attach a numeric target to each of several objectives, measure how far the plan misses each target, and minimise the misses you dislike. the philosophy is herbert simon’s satisficing¹ — real decision makers do not maximise a grand utility function, they set aspiration levels and stop when they are met — and the machinery is pure linear programming: goal programming was invented by charnes and cooper as an LP device² and remains the most-used technique in practical multi-criteria decision making precisely because it never leaves LP territory.

take a linear program and add one word — integer — and the complexity class jumps from polynomial to NP-hard. that word buys expressive power nothing continuous can match: yes/no decisions, either/or logic, fixed costs, sequencing, assignment. integer programming is the lingua franca of operations research precisely because “decide” is not a convex verb. 𐃏

single-objective optimisation is a polite fiction. real decisions trade cost against quality, return against risk, speed against accuracy — and the objectives disagree, otherwise you would not have listed them separately. 𐃏 multi-objective optimisation refuses to mash them into one number prematurely. the price of that honesty: “the optimum” stops being a point and becomes a set — the pareto front — and half the subject is about how to trace it, the other half about how to pick from it.

promote the objective of a linear program from a plane to a bowl and you get quadratic programming: minimise a quadratic function over a polyhedron. it is the smallest step beyond LP, yet it captures a startling share of applied mathematics — support vector machines, portfolio selection, ridge regression, model-predictive control — because “squared penalty subject to linear rules” is how half the world states its preferences. 𐃏

every linear program you have ever written down was a lie: the coefficients came from measurements, forecasts and vendor spreadsheets, and the optimal vertex — sitting, by design, on the boundary of the feasible region — shatters the moment any of them wobbles. 𐃏 robust optimisation is the pessimist’s response: declare a set \(\mathcal{U}\) of realisations you refuse to be hurt by, and demand feasibility for every member of it. no distributions, no expectations, no scenarios — just a set and a worst case. the surprise, and the reason the field exists, is that this worst case can usually be folded back into a deterministic problem of the same (or nearly the same) complexity class.¹

“programming” here means planning, not coding — the word predates the software sense. 𐃏 a linear program optimises a linear objective over a region carved out by linear inequalities. it is the base camp of mathematical programming: quadratic, integer and non-linear programming all generalise it in one direction or another, and all of them lean on LP machinery (relaxations, duals, warm starts) to get anything done. clrs devotes chapter 29 to it (Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford, 2009).