A coordinated effort to formalize the mathematics of operations research in Lean 4.
Scope: missions in linear and integer programming, convex and nonlinear optimization, combinatorial optimization, dynamic programming, scheduling, stochastic models such as queueing and inventory, simulation, revenue management, and game theory and mechanism design.
Fundamentals of Queueing Theory II: Erlang's Formulas and the Halfin–Whitt Square-Root Staffing LawTextbook
Every call center, hospital ward, cloud server pool and telephone exchange that is sized by formula is sized by one of a handful of explicit expressions from Markovian queueing theory. The two oldest are A. K. Erlang's: the Erlang-B (loss) formula of 1917, which gives the fraction of calls lost when c trunks carry an offered load of r erlangs, and the Erlang…
Fundamentals of Queueing Theory I: Foster's Criterion for Positive RecurrenceTextbook
Almost every model in queueing theory is analysed through a Markov chain. The number of customers in an M/M/c queue is a continuous-time birth–death chain; the number left behind by departing customers of an M/G/1 queue is a discrete-parameter chain on {0,1,2,…} (the imbedded Markov chain); networks of queues are chains on vectors of queue lengths.…
An Introduction to the Theory of Mechanism Design XI: Optimal Sequential Screening by Option ContractsTextbook
Many sales are contracted before the buyer knows what the good is worth to her. An airline sells a ticket months before the trip, a hotel sells a refundable or non-refundable room before the traveller's plans are settled, and a supplier signs a capacity contract before demand is realised. At the time of contracting the buyer holds some private information…
An Introduction to the Theory of Mechanism Design X: Robust Mechanism Design — Belief Revelation on Finite Type SpacesTextbook
Classical Bayesian mechanism design assumes that the designer knows the agents' beliefs about each other: typically a commonly known prior over independent private values. Wilson's critique (1987) observed that mechanisms tuned to such a prior can depend on details that no designer knows, and a literature on robust mechanism design replaced the fixed prior…
An Introduction to the Theory of Mechanism Design IX: Monotone Direct Mechanisms Are Dictatorial (Gibbard–Satterthwaite)Textbook
Voting rules, committee procedures and any other method that turns individual rankings into one collective choice face the same question: can the rule be designed so that no participant ever gains by misreporting their ranking? The Gibbard–Satterthwaite theorem (Gibbard, 1973; Satterthwaite, 1975) answers no. When at least three alternatives can be chosen…
An Introduction to the Theory of Mechanism Design VII: Crémer–McLean Full Surplus Extraction with Correlated TypesTextbook
Bayesian mechanism design asks which collective decisions and payments a designer can implement when every agent holds private information, the type, drawn from a commonly known prior. Most of the classical theory (Myerson's optimal auction, the Myerson–Satterthwaite impossibility, the public goods results) assumes that types are independent. Once types are…
Toward Robust Revenue Management: Competitive Analysis of Online Booking III: Bid-Price Controls Are Optimally 1/(1 − ln r)-CompetitiveResearch Paper
Revenue management decides how much of a fixed, perishable capacity (airline seats, hotel rooms) to sell, and at what price. Classical single-leg models assume a known demand distribution for each fare class and maximise expected revenue. Many carriers instead use bid-price controls: a request is accepted when its fare is at least a threshold ("bid price")…
Toward Robust Revenue Management: Competitive Analysis of Online Booking II: Nested Protection Levels Are Optimally 1/Δ-Competitive for m FaresResearch Paper
Airlines, hotels and rental firms sell a fixed stock of capacity to customers who arrive over time and pay different prices for the same unit. Classical revenue management, from Littlewood's two-fare rule (1972) to the dynamic programs of Brumelle and McGill (1993), decides how much capacity to hold back for high-fare customers from a demand forecast. When…
Toward Robust Revenue Management: Competitive Analysis of Online Booking I: The Nested Two-Fare Protection Level Is Optimally b(r)-CompetitiveResearch Paper
Revenue management decides how much of a fixed, perishable capacity (airline seats, hotel rooms) to sell at each price. The classical single-leg models, starting with Littlewood's two-fare rule (1972) and continued by Belobaba, Brumelle–McGill and Lee–Hersh, assume that demand for each fare class follows a known probability distribution and maximise…
Bellman's Dynamic Programming VIII: Multi-Stage Games, Games of Survival and the Extended Min-Max TheoremTextbook
Chapter X of Richard Bellman's Dynamic Programming (Princeton University Press, 1957; Princeton Landmarks edition 2010, DOI 10.2307/j.ctv1nxcw0f) carries the functional-equation method of the earlier chapters from one-player decision processes to two-player zero-sum games that are played over many stages. At each stage the two players make simultaneous…
Bellman's Dynamic Programming VII: Convergence of Discrete Approximations in the Calculus of VariationsTextbook
Chapter IX of Richard Bellman's Dynamic Programming (Princeton University Press, 1957; Princeton Landmarks edition 2010, DOI 10.2307/j.ctv1nxcw0f) recasts problems of the calculus of variations with constraints as dynamic programming processes. A variational problem with an inequality constraint on the control, such as 0≤y≤x, is awkward for the…
Linear Programming: Foundations and Extensions VI: The Homogeneous Self-Dual Predictor–Corrector MethodTextbook
Interior-point methods are the standard polynomial-time algorithms for linear programming, and the path-following method that practitioners implement (Chapter 18 of Vanderbei's Linear Programming: Foundations and Extensions) comes without a complete convergence proof. Chapter 22 of the same book presents a closely related algorithm for which a complete…
Minimization Methods for Non-Differentiable Functions IV: Linear Convergence of the Subgradient Method under Level-Set Shape ConditionsTextbook
The subgradient method minimizes a convex function f on Rn that need not be differentiable, by stepping against an arbitrary subgradient. With stepsizes hk→0, ∑hk=∞ it converges (Shor, Theorem 2.2), but in general only slowly: no stepsize rule that ignores the structure of f gives a geometric rate. Section 2.3 of N. Z. Shor's Minim…
Stochastic Dynamic Programming and the Control of Queueing Systems VI: The (SEN) Assumptions and the Average Cost Optimality InequalityTextbook
Queueing control problems (admission control, routing, service-rate selection, flow control) are naturally posed as Markov decision chains with a denumerably infinite state space, such as the number of customers in a buffer, and are usually judged by their long-run average cost per unit time. When the state space is finite, Chapter 6 of Sennott's book shows…
Makespan Minimization in Job Shops: A Linear Time Approximation Scheme: The Interval LP Is Feasible at the Restricted OptimumResearch Paper
The job shop scheduling problem asks for a nonpreemptive schedule of jobs on machines, each job a fixed sequence of operations with prescribed machines and processing times, that minimizes the time at which the last operation completes. It is one of the most studied hard problems of combinatorial optimization: even very constrained versions are strongly…
Analysis and Algorithms for Service Parts Supply Chains VII: Palm's Theorem for Nonstationary DemandTextbook
Spare-parts inventory models for repairable items rest on Palm's theorem: if demands arrive as a Poisson process with constant rate λ and each demanded unit spends an independent, identically distributed resupply time with mean τˉ in the pipeline, the number of units in resupply is Poisson with mean λτˉ in steady state. Stock levels,…
Elements of Queueing Theory V: Strassen's Theorems and the Stochastic Ordering of QueuesTextbook
Chapters 1–3 of Baccelli and Brémaud's Elements of Queueing Theory compute exact quantities:
Palm identities, stability criteria, PASTA, Pollaczek–Khinchin. Chapter 4 asks a different
question. When you cannot compute a queue, can you at least say it is better than another one?
Elements of Queueing Theory III: Stationary Regimes of Stochastic RecurrencesTextbook
Chapter 2 of Baccelli and Brémaud's Elements of Queueing Theory asks when a queue has a
stationary regime. §§2.1–2.4 answer it for the single-server and multiserver queues by Loynes'
monotone construction. §§2.5 and 2.11 answer it for the general object those constructions are
instances of: a stochastic recurrence
Elements of Queueing Theory II: The Loynes Stability Theorem and CouplingTextbook
Chapter 1 of Baccelli and Brémaud's Elements of Queueing Theory builds a calculus for stationary
queues. Chapter 2 asks the prior question: when is there a stationary queue at all?
Linear Programming: Foundations and Extensions IV: Existence of the Central PathTextbook
Interior-point methods solve linear programs by moving through the interior of the feasible region instead of along its edges, as the simplex method does. The methods used in practice are path-following methods: they track a curve, the central path, that runs through the interior of the feasible region and ends at an optimal solution. Before any such method…
Linear Programming: Foundations and Extensions II: Farkas' Lemma and Strict Complementary SlacknessTextbook
Every linear program comes with a second linear program, its dual, and most of what is known about linear programming is a statement about how the two interact. Weak duality gives certificates of optimality; strong duality says those certificates always exist; complementary slackness turns optimality into a system of equations. These three facts are the…
Minimization Methods for Non-Differentiable Functions XI: Convexity and Subgradients of the Value Function in Decomposition with Respect to VariablesTextbook
Large convex programs often have a block structure: a small set of "complicating" variables x couples otherwise separate subproblems in the remaining variables y. Decomposition with respect to variables fixes x, solves the subproblem in y, and treats the optimal subproblem value as a function of x alone. The outer problem in x is then small but nonsmooth,…
Minimization Methods for Non-Differentiable Functions X: The Space-Dilation Ellipsoid Method Localizes the Solution in Ellipsoids Shrinking by the Ratio q_nTextbook
The ellipsoid method is the algorithm that settled the polynomial-time solvability of linear programming (Khachiyan, 1979) and that underlies the equivalence of separation and optimization in combinatorial optimization (Grötschel, Lovász and Schrijver, 1981). Its origin is in nonsmooth convex optimization. In 1976 Yudin and Nemirovskii proposed a modified…
Minimization Methods for Non-Differentiable Functions II: Convex Functions Are Almost Differentiable and Their Almost-Gradients Are SubgradientsTextbook
Gradient methods assume a continuous gradient; subgradient methods assume convexity. Many objective functions met in practice satisfy neither. Shor's example is economic planning, where components of the objective are piecewise-smooth, not necessarily convex functions of a parameter describing the productivity of a unit, and where minimax formulations…
Stochastic Dynamic Programming and the Control of Queueing Systems XIII: Lyapunov Criteria and z Standard Markov Chains with CostsTextbook
Average cost control of queues rests on a small amount of Markov chain theory: when does a chain with costs have a well defined long-run average cost, and how can that be checked for a concrete model with an unbounded state space? Appendix C of L. I. Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999, doi:10.1002/9780470…