01
min cᵀx s.t. Ax = b, x ≥ 0
Linear program — standard (primal) form
Choose the decision vector x to minimize a linear cost c·x while satisfying linear balance constraints Ax = b and non-negativity. The workhorse model for allocation, blending, staffing and scheduling; solved by the simplex or interior-point methods.
Origins & use Formulated by Leonid Kantorovich in 1939 for Soviet production planning and independently by George Dantzig in 1947, whose simplex method made it solvable at scale for U.S. Air Force logistics; Kantorovich and Koopmans shared the 1975 Nobel in economics for it. Today it plans refinery blends, airline crews, supply chains and technician hours.
02
max bᵀy s.t. Aᵀy ≤ c
Linear program — dual form
Every LP has a mirror problem whose variables y are shadow prices: the marginal value of one more unit of each resource in b. At the optimum the dual's value equals the primal's (strong duality), so it prices every constraint.
Origins & use John von Neumann conjectured LP duality in a 1947 conversation with Dantzig; Gale, Kuhn and Tucker proved it in 1951. Its shadow prices are what Excel Solver's sensitivity report shows and what economists call the marginal value of a resource — the price of capacity, budgets and bottlenecks.
03
L(x, λ) = f(x) + λᵀg(x)
Lagrangian
Folds the constraints g(x) into the objective f(x) using multipliers λ — prices charged for violating each rule. It is the bridge between constrained and unconstrained optimization and the source of duality theory.
Origins & use Joseph-Louis Lagrange introduced the multipliers in Mécanique analytique (1788) to handle constrained motion in mechanics. Two centuries later the same device gives economics its marginal-value reading of constraints, gives machine learning the dual form of support-vector machines, and gives integer programming Lagrangian relaxation (Held and Karp, 1970) for hard routing problems.
04
∇f(x*) + Σᵢ λᵢ ∇gᵢ(x*) = 0
KKT stationarity condition
At an optimal point x*, the pull of the objective is exactly balanced by a weighted combination of the active constraints. In plain terms: you cannot improve any further without pushing against a rule that is already tight.
Origins & use Derived by William Karush in his 1939 master's thesis and rediscovered by Harold Kuhn and Albert Tucker in 1951, whose names the conditions carried alone for decades. They extend Lagrange to inequality constraints and are what every nonlinear and convex solver is actually trying to satisfy — from Markowitz portfolio optimization (1952) to today's interior-point methods.
05
λᵢ gᵢ(x*) = 0, λᵢ ≥ 0
Complementary slackness (with dual feasibility)
For each constraint, either it is binding or its price is zero — never both. A resource with slack has no marginal value; a binding one carries a positive shadow price. This is how a solver tells you which rules actually drive the plan.
Origins & use Part of the 1951 duality and Kuhn–Tucker results; in general-equilibrium economics (Arrow and Debreu, 1954) it is the rule that a good in excess supply has a zero price. Interior-point methods (Karmarkar, 1984; Mehrotra, 1992) work by driving the products λᵢgᵢ toward zero, and analysts use it daily to read which constraints bind in a sensitivity report.
06
cᵀx ≥ bᵀy
Weak duality
The cost of any feasible plan is at least the value of any feasible dual solution. The difference between the two is a guaranteed bound on how far the plan is from optimal — the basis of optimality certificates.
Origins & use An immediate consequence of the 1947–1951 duality work, and the reason a solver can prove optimality rather than merely assert it: any dual solution bounds every primal one. It powers the bounding step of branch-and-bound (Land and Doig, 1960) and the primal-dual method behind many approximation algorithms.
07
x₍ₖ₊₁₎ = xₖ − αₖ ∇f(xₖ)
Gradient descent
Move from the current point x_k a step of size α along the direction of steepest decrease of f. The core iteration behind training machine-learning models and large-scale continuous optimization.
Origins & use Proposed by Augustin-Louis Cauchy in 1847 for solving systems of equations; its stochastic variant (Robbins and Monro, 1951) and backpropagation (Rumelhart, Hinton and Williams, 1986) made it the engine of modern machine learning. Virtually every neural network, including today's large language models, is trained with a descendant of this line, such as Adam (2014).
08
x₍ₖ₊₁₎ = xₖ − [∇²f(xₖ)]⁻¹ ∇f(xₖ)
Newton's method
Uses curvature (the Hessian, ∇²f) as well as slope to jump toward the minimum, converging in far fewer iterations than gradient descent when second derivatives are available. It underlies interior-point solvers for LP and QP.
Origins & use Isaac Newton described the iteration around 1669 and Joseph Raphson simplified it in 1690; Thomas Simpson extended it to systems and to optimization in 1740. It is the inner loop of modern interior-point solvers (Karmarkar, 1984; Nesterov and Nemirovski, 1994) and, through quasi-Newton variants such as BFGS (1970), of large-scale statistical model fitting.
09
V(s) = maxₐ [ r(s,a) + γ Σ P(s′|s,a) V(s′) ]
Bellman equation
The value of being in state s equals the best available immediate reward plus the discounted expected value of the state that follows. The foundation of dynamic programming, Markov decision processes and reinforcement learning — decisions made over time under uncertainty.
Origins & use Richard Bellman developed dynamic programming at the RAND Corporation in the early 1950s (book, 1957), reputedly choosing the name to sound harmless to a research-averse Secretary of Defense. It underlies inventory and equipment-replacement policies, shortest-path routing (Bellman–Ford, 1958), American option pricing, and reinforcement learning from Q-learning (1989) to AlphaGo (2016).
10
x ∈ {0,1}ⁿ
Binary decision variables
Each decision is a yes/no: assign or don't, open or don't, build or don't. Binary variables turn a linear program into a mixed-integer program — where assignment, dispatch and scheduling problems live, and where most of the computational difficulty comes from.
Origins & use Integer programming began with Dantzig, Fulkerson and Johnson's 1954 solution of a 49-city traveling-salesman problem, Gomory's cutting planes (1958) and Land and Doig's branch-and-bound (1960). Yes/no variables now drive airline crew scheduling, power-plant unit commitment, facility location, kidney-exchange matching and technician dispatch.
11
Σⱼ aᵢⱼ xⱼ ≤ bᵢ for all i
Capacity (knapsack-type) constraints
Each resource i — a tech-day's minutes, a budget, a machine's hours — cannot be consumed beyond its limit b_i by the decisions x_j that draw on it (a_ij is how much decision j uses of resource i). The general form of the minutes-per-tech-day rule in the maintenance scheduler.
Origins & use The knapsack problem's name goes back to Tobias Dantzig's early-twentieth-century lectures; Karp proved it NP-complete in 1972, and Lorie and Savage (1955) framed capital budgeting in exactly this form. The same inequality governs cargo loading, Gilmore and Gomory's cutting-stock work (1961), cloud-server bin packing and minutes per technician per day.
12
gap = (z_UB − z_LB) / |z_UB|
Relative optimality gap
How far the best plan found (z_UB, the incumbent in a minimization) is from the best proven bound (z_LB) that no plan can beat, as a fraction. A solver reports 0% when it has proven optimality and stops at a tolerance otherwise — the honest measure of how good a plan is.
Origins & use Comes with branch-and-bound (Land and Doig, 1960; Dakin, 1965), which always carries both a best-found plan and a best proven bound. Commercial and open-source MIP solvers — CPLEX, Gurobi, HiGHS — use the gap as their stopping rule and headline quality metric; it is the number that lets a planner say a schedule is within 1% of the best possible, with a proof behind it.