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.
Discrete Convex Analysis XVIII: Integral Convexity of Minimizer SetsTextbook
A classical convex function's global minimality is equivalent to its local minimality — the
single fact that makes convex optimization tractable, since checking a small neighborhood
suffices to certify a global guarantee. The discrete analogue is not automatic: a function on
the integer lattice can fail to have any well-behaved "local" notion at all, and…
Discrete Convex Analysis XVII: Fenchel Duality and Linear-Programming IntegralityTextbook
Duality is the organizing principle of convex optimization: a minimization problem's optimal
value equals a maximization problem's optimal value, and this coincidence, rather than being a
lucky accident, follows from a separating-hyperplane argument that applies whenever the two
problems' feasible regions are shaped compatibly enough. Werner Fenchel…
Markov Decision Processes VII: Consumption-Investment Problems and Regime SwitchingTextbook
Real investors do not merely accumulate wealth for a single terminal payoff; they consume along
the way, and the market they invest in is rarely a single fixed statistical regime for years at
a time — bull and bear markets, business cycles, and volatility regimes shift the distribution
of returns. Bäuerle and Rieder's §4.3 extends the terminal-wealth theory…
Maximizing Non-Monotone Submodular Functions V: Beating 1/2 for Symmetric Functions Requires Exponentially Many Value QueriesResearch Paper
Maximizing a nonnegative submodular set function without constraints contains Max Cut, Max Directed Cut and facility-location problems as special cases. In the value-oracle model an algorithm knows nothing about the function except the values f(S) of the sets S it queries, and it is judged by the number of queries it makes. Feige, Mirrokni and Vondrák (SIAM…
Lifts of Convex Sets and Cone Factorizations II: Antichain and Face-Count Lower Bounds on the Nonnegative Rank of a PolytopeResearch Paper
Many polytopes that arise in combinatorial optimization, such as the matching, cut, stable set and travelling salesman polytopes, have exponentially many facets, yet some of them can be written as the linear projection of a polyhedron with far fewer facets. The smallest number of facets of such a lift decides whether the polytope admits a compact…
Maximizing Non-Monotone Submodular Functions IV: Smooth Local Search Achieves 2/5 of the OptimumResearch Paper
Many optimization problems ask for a subset of a finite ground set that maximizes a submodular function, a set function with diminishing marginal returns. Max Cut and Max Directed Cut in graphs, facility location with fixed costs, and the maximization of mutual information or entropy of a subset of random variables are all of this form. Unlike the monotone…
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…