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.
On Polyhedral Approximations of the Second-Order Cone II: A Lower Bound on the Size of Polyhedral ApproximationsResearch Paper
A conic quadratic program minimizes a linear objective subject to constraints of the form ∥Aℓx−bℓ∥2≤cℓTx−dℓ. Interior-point methods solve such programs in polynomial time, but around 2000 the available solvers handled far smaller instances than linear programming codes did. Ben-Tal and Nemirovski (Math. Oper. Res. 26(2), 2001) asked…
Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix IV: Sample Bound for Hutchinson's Trace EstimatorResearch Paper
Many computations need the trace of a matrix A that is never formed explicitly and can only be applied to vectors: the trace of a matrix function such as trace(A−1) or logdetA=trace(logA) in statistics and lattice QCD, the Frobenius norm ∥B∥F2=trace(BTB) of an operator, or the number of triangles of a graph. The…
Markov Decision Processes II: Existence of Optimal Policies under Compactness and ContinuityTextbook
The finite-horizon theory of chunk 02a-model-bellman-equation (Bäuerle and Rieder's Theorem
2.3.8, the Structure Theorem) reduces the existence of an optimal policy and the validity of the
Bellman equation to a single abstract hypothesis: the Structure Assumption (SAN), the existence
of function classes IMn and decision-rule classes Δn closed…
Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix II: Exact Rank of a Projection Matrix from the Gaussian Trace EstimatorResearch Paper
Many matrices in scientific computing are available only implicitly: one can multiply a vector by A, for instance by solving a linear system or applying a matrix function, but the entries of A are never formed. Quantities such as the trace must then be estimated from a small number of matrix–vector products. Randomized trace estimators do exactly this: draw…
Monotonic Solutions of Cooperative Games 1: For Five or More Players No Core Allocation Rule Is Coalitionally MonotonicResearch Paper
Cooperative games model the division of a jointly produced surplus, or a jointly incurred cost, among the participants of an enterprise: towns sharing a water supply system, divisions of a firm sharing overhead, members of a consortium sharing the savings of joint investment. In such applications allocations are rarely fixed once and for all. Costs and…
Processing Networks XI: Maximal Stability of Workload-Weighted Task AllocationTextbook
Large-scale data-intensive computing splits a job into many small "map tasks," each of which must
be assigned to one of thousands of general-purpose servers in a data center — the MapReduce
paradigm introduced by Dean and Ghemawat (2008). Because a task's input data is stored on only a
few of those servers, routing it to a server that already holds its data…
Optimal Policy for a Multi-Product, Dynamic, Nonstationary Inventory Problem: The Base Stock Ordering Policy Is OptimalResearch Paper
An inventory manager who stocks many products, faces random demand and pays ordering, holding and shortage costs must decide each period how much of each product to order. In general the optimal decision depends on the whole state and is found by solving a dynamic programme, which becomes impractical as the number of products grows. Myopic (or base stock)…
Processing Networks X: Maximal Stability of Proportionally Fair ControlTextbook
Mission IX (09-proportional-fairness-core) formalized proportional fairness (PF) as a control
policy and proved the technical core of its stability theory: under a load condition, the PF
fluid model is stable (Theorem 10.5), via an entropy Lyapunov function that is genuinely not
Lipschitz continuous — a departure from every other stability argument in J. G.…
An Overview of Pricing Models for Revenue Management: Performance Guarantee of the Deterministic Price Heuristic in Periodic-Review PricingResearch Paper
Dynamic pricing under limited inventory is a core problem of revenue management: a seller holds C0 units of a perishable product (airline seats, hotel rooms, seasonal goods) and must choose prices over a finite selling horizon while demand is random and responds to price. The exactly optimal policy solves a stochastic dynamic program whose state is the…
Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs: Binding Cuts Force Degenerate Descendant Problems in Nested DecompositionResearch Paper
Multistage stochastic linear programs model decisions taken in periods t=1,…,T while a random vector ξt is revealed period by period: production and capacity planning, energy scheduling, asset–liability management. With finitely many scenarios the problem is one very large linear program with a tree structure, and decomposition methods solve it…
Santa Claus Schedules Jobs on Unrelated Machines: The Configuration LP Has Integrality Gap at Most 33/17Research Paper
Scheduling jobs on unrelated machines so as to minimize the makespan (the time at which the last machine finishes) is one of the central problems of approximation algorithms. For the general problem, Lenstra, Shmoys and Tardos (1990) gave a 2-approximation and showed that no polynomial-time algorithm achieves a factor below 3/2 unless P = NP; closing the…
Processing Networks IX: Fluid Stability of the Proportionally Fair AllocationTextbook
Every control policy formalized so far in this series — HLSPS (mission VI), back-pressure/
max-weight (mission VIII) — allocates service effort to entire job classes as indivisible units.
Proportional fairness takes a different starting point: it is a general-purpose recipe for
dividing a shared, continuously divisible resource among competing demands,…
The Assignment Game I: The Core 1: The Core Is the Set of Optimal Solutions of the Dual Assignment LPResearch Paper
A two-sided market in which each participant trades with at most one partner on the other side — houses and buyers, workers and firms, producers and consumers under exclusive bilateral contracts — is the setting of L. S. Shapley and M. Shubik's assignment game (Int. J. Game Theory 1 (1971) 111–130). Money is transferable, so the natural solution concept is…
Learnability, Stability and Uniform Convergence I: A Problem Is Learnable if and only if It Admits a Uniform-RO Stable Universal AERMResearch Paper
In supervised binary classification, a hypothesis class is learnable if and only if it has uniform convergence, meaning that empirical risks converge to true risks uniformly over the class. When that holds, empirical risk minimisation (ERM) learns. This equivalence, due to Vapnik and Chervonenkis and extended to real-valued losses by Alon, Ben-David,…
Processing Networks V: Lyapunov Stability Criteria for Fluid ModelsTextbook
Mission III's Theorem 6.2 reduces SPN stability to a question about deterministic fluid model
solutions: does every solution of a fixed system of equations get driven to the origin,
uniformly in its starting size? Mission IV showed how to derive the extra, policy-specific
equations a fluid model must satisfy. What remains is a method for proving that a…
On the Optimality of Generalized (s, S) Policies: A Generalized (s, S) Policy Is Optimal in Every Period of the Finite-Horizon Inventory ProblemResearch Paper
In a periodic-review inventory system a manager observes the stock level before ordering, decides how much to order, and then faces random demand. When ordering costs a fixed setup charge plus a constant price per unit, Scarf (1960) proved that an (s,S) policy is optimal in every period of a finite-horizon problem: order up to S when the stock falls below s,…
A Dynamical Approach to an Inertial Forward-Backward Algorithm for Convex Minimization: The IFB Iterates Minimize the Objective and Converge Weakly to a MinimizerResearch Paper
Many problems in signal processing, statistics and operations research ask to minimize a sum Θ=Φ+Ψ of a nonsmooth convex term Φ (a constraint indicator, an ℓ1 penalty) and a smooth term Ψ. The standard method is the forward-backward (proximal-gradient) algorithm: an explicit gradient step on Ψ followed by a proximal step on Φ.…
Three Partition Refinement Algorithms 1: Distinguishing-Prefix Refinement Finds Every Distinguishing Prefix Within m′ Refinement StepsResearch Paper
Sorting a collection of strings in lexicographic order is a basic subroutine in compilers, string indexing, suffix sorting and the construction of tries. The classical method, due to Aho, Hopcroft and Ullman (The Design and Analysis of Computer Algorithms, 1974), is a multipass radix sort that processes the strings from the last position to the first and…
Dual Stochastic Dominance and Related Mean-Risk Models 1: Second-Degree Stochastic Dominance Is Dominance of Absolute Lorenz CurvesResearch Paper
Comparing uncertain outcomes is the basic problem of decision making under risk. Second-degree stochastic dominance (SSD) is the comparison that every risk-averse decision maker who prefers larger outcomes agrees with: X dominates Y in this sense exactly when EU(X)≥EU(Y) for every nondecreasing concave utility U for which the…
Processing Networks III: Fluid Model Stability Implies SPN StabilityTextbook
A stochastic processing network (SPN) — buffers holding waiting work, activities that
consume items from buffers and produce items into others, driven by stochastic arrivals and
service requirements — is stable, in the sense of mission I's Definition 3.6, exactly when its
ambient Markov chain is positive recurrent. That definition is correct, but it is a…
λ1, Isoperimetric Inequalities for Graphs, and Superconcentrators 2: Cayley Graphs of Finite Quotients of a Property (T) Group Are Linear EnlargersResearch Paper
An expander is a sparse graph in which every set of vertices has many neighbours outside itself. Expanders are the building blocks of superconcentrators (sparse directed graphs that route any r inputs to any r outputs along vertex-disjoint paths), of sorting and switching networks, and of many constructions in complexity theory and coding; the survey of…
Robust Control of Markov Decision Processes with Uncertain Transition Matrices 4: The Dual of the Worst-Case Expectation over a Kullback-Leibler BallResearch Paper
A robust Markov decision process replaces the unknown transition probabilities of an MDP by sets of plausible values and optimises against the worst case. Nilim and El Ghaoui (Oper. Res. 53 (2005)) showed that, when the uncertainty is rectangular (each row of each transition matrix varies independently in its own set), the robust problem is solved by a…
λ1, Isoperimetric Inequalities for Graphs, and Superconcentrators 1: A Diameter Bound from λ1Research Paper
The eigenvalues of the Laplacian of a graph carry metric information about the graph. The second-smallest one, λ1(G), was named the algebraic connectivity by Fiedler (Fiedler 1973), who showed it is positive exactly for connected graphs. N. Alon and V. D. Milman (J. Combin. Theory Ser. B 38 (1985) 73–88) showed that a large λ1 also forces two…
Robust Control of Markov Decision Processes with Uncertain Transition Matrices 3: Stationary Policies Suffice and the Stationary/Time-Varying Uncertainty Gap Vanishes GeometricallyResearch Paper
A Markov decision process (MDP) is controlled with transition probabilities estimated from data, and optimal policies computed for the estimated model can perform badly when the estimates are off. Robust MDPs replace the single transition model by a set of models and optimize the worst case over that set. Two readings of "the set" are possible. In the statio…
Processing Networks I: The Equivalence of SPN StabilityTextbook
A stochastic processing network (SPN) is the general model behind manufacturing lines,
call centers, computer systems, communication networks and hospital wards: a collection of
buffers holding waiting work, a collection of activities (servers) that consume items from
buffers and produce items into others, and stochastic primitives — arrival processes and…