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.
Local Search Heuristics for k-Median and Facility Location Problems IV: Local Search with Multi-Copy Moves for Capacitated Facility Location Has Locality Gap 4Research Paper
Facility location asks where to open service points (warehouses, plants, servers) and how to connect customers to them so that the total opening cost plus the total connection cost is minimum. In the capacitated version each facility can serve only a limited number of customers, which is the situation in most applications: a warehouse has a floor area, a…
Local Search Heuristics for k-Median and Facility Location Problems I: Single-Swap Local Search for k-Median Has Locality Gap 5Research Paper
The k-median problem asks where to open k facilities so that the total distance from a set of clients to their nearest open facility is as small as possible. It is a basic model of facility location in operations research (placing depots, warehouses or servers) and of clustering with representative centres, and it is NP-hard, so the question of interest is…
Coherent Multiperiod Risk Adjusted Values and Bellman's Principle: Stability of the Test Probabilities Is Equivalent to Bellman's PrincipleResearch Paper
A coherent risk measure assigns to a future financial position the smallest amount of capital that makes it acceptable to a supervisor. Artzner, Delbaen, Eber and Heath characterised the one-period version: every coherent risk measure has the form π(X)=infQ∈PEQ[X] for a set P of test probabilities (ADEH…
Multi-armed Bandit Allocation Indices VI: Bandit Sampling Processes, Favourable Priors and Invariance of the IndexTextbook
The bandit processes that motivated the index theorem are sampling processes: an arm is a population from which one draws i.i.d. observations whose distribution has an unknown parameter, and each draw both earns something and teaches something. Chapter 7 of Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/97804709800…
Multi-armed Bandit Allocation Indices V: Restless Bandits, Indexability and Whittle Indices for Monotone ModelsTextbook
Every proof of the index theorem in Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/9780470980033), uses the fact that a bandit not being processed is frozen. Chapter 6 drops that: Whittle's restless bandits evolve under the passive action too, by a different law, and m of n must be active at every time. The…
Multi-armed Bandit Allocation Indices IV: The Achievable Region, Generalized Conservation Laws and the Adaptive Greedy AlgorithmTextbook
Chapter 5 of Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/9780470980033), presents the achievable region methodology of Tsoucas, Bertsimas and Niño-Mora, Glazebrook and Garbe, and Dacre, Glazebrook and Niño-Mora: instead of arguing about policies, one argues about the set of performance vectors they can produce.…
Introduction to Multi-Armed Bandits XI: Bandits and Agents, Incentivized Exploration via Hidden ExplorationTextbook
A recommendation system learns from the users it serves: the diner who tries a restaurant produces the review the next diner reads. Each user would rather exploit what is already known than explore for the benefit of those who come later, so a population of self-interested agents under-explores, and an alternative that looks bad on sparse early evidence may…
The Theory and Practice of Revenue Management IV: AuctionsTextbook
Airlines selling last seats, Priceline's name-your-own-price, procurement of supply contracts:
Chapter 6 of Talluri and van Ryzin's The Theory and Practice of Revenue Management
(2004) treats auctions as pricing mechanisms and asks what
revenue they earn and how to design them. Its centre is Myerson's
(1981) theory for independent private values: whatever…
Inventory Control VIII: The Clark-Scarf Decomposition for a Serial SystemTextbook
Chapter 10 of Axsäter's Inventory Control turns to reorder points and safety stocks in
multi-echelon systems, where the installations cannot be treated separately: a large stock
downstream lets an upstream site run lean, and a long upstream lead-time argues for stock at
the top. The best-known exact technique for serial systems is the decomposition of Clark…
Fundamentals of Supply Chain Theory VI: Pooling and FlexibilityTextbook
A firm that holds inventory in five warehouses needs more safety stock than one that holds the
same inventory in one warehouse, because the demands of five regions do not all run high at
once. Eppen (1979) made this precise for a multi-location
newsvendor and gave it its name, the risk-pooling effect. Chapter 7 of Snyder and Shen's
Fundamentals of Supply…
Fundamentals of Supply Chain Theory V: The Bullwhip EffectTextbook
Procter & Gamble observed in the 1990s that the orders its distributors placed for diapers were
far more variable than the retail sales of diapers, and that its own orders to suppliers were more
variable still, although the end demand for diapers is about as stable as demand gets. The
phenomenon, a growing amplification of variability as one moves upstream…
Markov Decision Processes III: The Average Reward Optimality Equation for Unichain ModelsTextbook
When a system is controlled indefinitely and decisions are frequent — a router admitting
packets, a queue accepting jobs, a machine being maintained — discounting future rewards is
often unjustified, and what matters is the long-run average reward per period. Puterman's
Chapter 8 (doi:10.1002/9780470316887) develops the
theory of this criterion, and its…
Convex Polytopes V: Recognition from projections (GRU-M05-PROJECTION-RECOGNITION)Textbook
A convex set can be studied through its images in spaces of smaller dimension. Each image records part of the geometry, while losing the information along the directions that are collapsed. A finite convex hull always has finite convex hulls as its affine images. The converse asks whether sufficiently rich projection data can force the original set to have…
Markov Processes: Characterization and Convergence IV: Martingale characterization of Markov processesTextbook
A stochastic process can be described through the way functions of its state change over time. For a suitable pair of functions f and g, the difference between f evaluated along the process and the accumulated integral of g has zero conditional drift. A martingale problem specifies a collection of such pairs. The question is whether these local conditions…
Resource Allocation and Cross-Layer Control in Wireless Networks III: Lyapunov Optimization for Utility and FairnessTextbook
Chapters 3-4 of Georgiadis, Neely & Tassiulas's survey Resource Allocation and Cross-Layer
Control in Wireless Networks (Foundations and Trends in Networking, 2006) answer "can the
network stay stable?" — the backpressure algorithm's throughput optimality (Theorem 4.5) says
yes, for any arrival rate inside the capacity region. But networks are usually…
Resource Allocation and Cross-Layer Control in Wireless Networks II: The Dynamic Backpressure AlgorithmTextbook
Every stability result in Georgiadis, Neely & Tassiulas's survey Resource Allocation and
Cross-Layer Control in Wireless Networks (Foundations and Trends in Networking, 2006) — the
throughput optimality of the dynamic backpressure algorithm (Theorem 4.5), the utility-optimal
Lyapunov drift bound of Chapter 5, the energy-constrained control algorithm of…
Convex Polytopes XVIII: Complete characterization of simplicial face vectorsTextbook
A convex polytope has finitely many faces in each dimension, and their numbers form its f-vector. Determining which integer vectors occur is a basic realization problem in discrete geometry: necessary identities such as Euler's relation do not by themselves decide whether a proposed vector comes from a polytope. For simplicial polytopes, whose facets are…
The Design of Competitive Online Algorithms via a Primal-Dual Approach VI: Maximizing Ad-Auctions RevenueTextbook
Search-engine ad-auctions sell items (ad slots) to buyers who arrive with per-item bids and a
fixed daily budget, online: each item must be allocated the moment it appears, with no ability to
revisit past allocations, and no buyer may ever be charged more than its budget. Buchbinder and
Naor's survey [1] models this as a generalization of online bipartite…
Convex Polytopes X: Recognition from projectionsTextbook
A convex set can be studied through its images in lower-dimensional spaces. Each image retains part of the geometry while discarding information along the directions that are collapsed. Finite convex hulls behave well under affine maps: the image of a convex hull of finitely many points is again the convex hull of finitely many points. The converse is…
Convex Polytopes V: Face-lattice recovery from ray queriesTextbook
A polytope can be given by a list of vertices, a list of inequalities, or much less explicit access. The last case arises when geometric information is available through queries to a physical or computational object but a full description is unavailable. Grünbaum's account of a result by Gritzmann, Klee, and Westwater asks how much of a polytope can be…
Foundations of Machine Learning XIV: Finite Markov Decision Processes and Bellman's EquationsTextbook
Reinforcement learning formalizes a scenario supervised learning cannot: an agent that
actively interacts with an environment, choosing actions that change both the state it
observes next and the reward it receives, rather than passively receiving an i.i.d. labeled
sample. Every practical treatment of this scenario — from classical dynamic programming to…
First-Order and Stochastic Optimization Methods for Machine Learning I: The Separation Theorem, Strong Duality and the KKT ConditionsTextbook
Every convex optimization algorithm in machine learning — from projected gradient descent to
support vector machines to the mirror-descent methods of later chapters of this book — is
justified by a small set of optimality certificates: a checkable condition on a candidate
solution that guarantees it actually solves the problem, without searching the whole…
High-Dimensional Probability XI: Dvoretzky-Milman's TheoremTextbook
A striking fact discovered by Dvoretzky in the 1960s (conjectured by Grothendieck, and sharpened
into its modern quantitative form by Milman in 1971) is that every high-dimensional convex body,
however irregular, contains a round slice: a random low-dimensional section (or projection) of
any bounded convex set in Rn is, with high probability, close…
Support Vector Machines V: Bernstein's Inequality for Independent Hilbert-Space-Valued Random VariablesTextbook
Every statistical guarantee for a learning algorithm ultimately rests on a concentration
inequality: a bound on how far an empirical average can stray from its expectation. For
real-valued averages, Bernstein's inequality (1924, refined through the 20th century) is the
classical tool — sharper than Hoeffding's inequality whenever the summands' variance is…