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.
Stochastic Convex Programming: Basic Duality 1: With Bounded Constraint Sets the Two-Stage Stochastic Convex Program Satisfies min P = sup DResearch Paper
A two-stage stochastic program with recourse models a decision taken in two steps: a first-stage decision is fixed before a random outcome is observed, and a second-stage (recourse) decision is chosen after the outcome is known, both subject to constraints and both incurring costs. The model is the standard framework for planning under uncertainty in…
The Geometry of Graphs and Some of Its Algorithmic Applications 3: The Complete Graph Kₙ Has Isometric Dimension ⌈log₂ n⌉Research Paper
An isometric model of a graph assigns vectors to vertices so that vector distances reproduce shortest-path distances exactly. The choice of norm matters: a graph that needs many Euclidean coordinates may admit a smaller realization under a different norm. Linial, London, and Rabinovich used this freedom to study the dimension of graph metrics and related…
Modified Policy Iteration Algorithms for Discounted Markov Decision Problems: From Bv₀ ≥ 0, Order-k Iterates Satisfy ‖v* − v_{n+1}‖ ≤ min{λ, λ(1−λᵏ)/(1−λ)‖P_n − P*‖ + λ^{k+1}}‖v_n − v*‖Research Paper
Discounted Markov decision problems are solved in practice by two classical schemes. Value iteration (successive approximations) is cheap per step but contracts the error only by the discount factor λ per step, which is slow when λ is close to 1. Policy iteration (Howard, 1960) converges in few steps, but each step solves a linear system for the…
The Weighted Majority Algorithm 2: On Any Partition into Segments, WML Makes at Most Σ min(l_i, (log(n/(βγ)) + m_i log(1/β))/log(1/u)) MistakesResearch Paper
Prediction with expert advice asks a master algorithm to combine the binary predictions of a pool of n prediction algorithms, trial after trial, so that it makes few more mistakes than the best member of the pool, without any probabilistic assumption on the data. Littlestone and Warmuth's Weighted Majority Algorithm WM (Littlestone and Warmuth 1994) keeps a…
Dependent Central Limit Theorems and Invariance Principles: A Martingale Difference Array with L²-Bounded Maximum Tending to 0 and Sum of Squares → 1 in Probability Is Asymptotically N(0, 1)Research Paper
The classical central limit theorem concerns sums of independent summands. Most sums that arise in statistics and applied probability are not independent: estimating equations of time-series models, stochastic approximation iterates, additive functionals of Markov chains, sequential test statistics. The standard route to asymptotic normality for such sums…
A Functional Equation and Its Application to Resource Allocation and Sequencing Problems 2: Under Precedence Constraints, All Deadlines Can Be Met iff They Are Met in Order of Modified DeadlinesResearch Paper
A single machine must process n jobs, each with a processing time and a deadline, and some jobs must be finished before others may start. The first question of any planner is whether the deadlines can be met at all. Without precedence constraints the answer is classical: Jackson's rule (J. R. Jackson, 1955, reported by W. E. Smith, 1956) says that all jobs…
The Tight Constant in the Dvoretzky–Kiefer–Wolfowitz Inequality I: P(√n sup(F − F̂ₙ) > λ) ≤ exp(−2λ²) for λ ≥ min(√(log 2/2), 1.0841 n^(−1/6))Research Paper
The Kolmogorov–Smirnov statistics measure how far the empirical distribution of a sample lies from a hypothesised distribution. They are the standard goodness-of-fit test for continuous data, and their tail probabilities are the basic tool for confidence bands around a distribution function. A test is only usable at a fixed sample size if those tail…
Some Monotonicity Results for Partially Observed Markov Decision Processes: MLR-Monotone Optimal Values and the Myopic Policy as a Lower Bound on the Optimal PolicyResearch Paper
A partially observed Markov decision process (POMDP) models a controller that cannot see the state of the system it controls. It sees only noisy observations, and so it acts on a belief: a probability vector over the hidden states. Machine maintenance, medical screening, quality control and search problems all have this form. The dynamic program of a POMDP…
Stochastic Estimation of the Maximum of a Regression Function: The Kiefer–Wolfowitz Iterates z_n Converge in Probability to the Maximizer θResearch Paper
Many problems in statistics, engineering and operations research ask for the input level x at which an unknown response function is largest, when the response can only be measured with noise: the dose that maximizes a yield, the setting that maximizes throughput in a simulation, the parameter that maximizes an expected reward. Robbins and Monro (1951) had…
Job Matching, Coalition Formation, and Gross Substitutes 1: Under Gross Substitutes the Salary-Adjustment Process Reaches a Discrete Core Allocation in Finitely Many RoundsResearch Paper
Labor markets match workers to firms, and the terms of each match (the salary) are negotiated along with the match itself. A firm's output depends on the whole team it hires, so a firm cares about sets of workers, not individual workers one at a time. Kelso and Crawford (1982) asked when such a market has a stable outcome, the core, in which no firm and…
Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain: In GI/M/s, a Positive Wait Is Exponential and a Positive Queue GeometricResearch Paper
A many-server queue in which customers arrive at the epochs of a renewal process and are served for exponential times is the basic model of a telephone exchange, a call centre, or a bank of identical machines. Its continuous-time queue-length process is not Markovian unless the arrivals are Poisson, so Erlang's birth–death formulas for M/M/s do not apply.…
The Fritz John Necessary Optimality Conditions in the Presence of Equality and Inequality Constraints: Every Minimizer of a C¹ Program Admits Multipliers (ū₀, ū, v̄) ≠ 0 with ū ≥ 0Research Paper
For problems with inequality constraints only, F. John (1948) showed that every minimizer admits nonnegative multipliers (uˉ0,uˉ1,…,uˉm)=0, one of which belongs to the objective. The Kuhn–Tucker conditions (1951) are the stronger statement in which the objective's multiplier can be taken equal to one; they need a constraint…
Stochastic Inequalities on Partially Ordered Spaces 1: Stochastically Ordered Initial Laws and Kernels Give Coupled Random Sequences with Xₙ ≤ Yₙ for All n Almost SurelyResearch Paper
Comparison theorems for stochastic processes answer a practical question: if one system starts "lower" and moves "upward" less aggressively than another, does it stay below the other one for all time? Queueing, reliability and inventory models use such statements to order performance measures of two systems without computing either distribution. Results of…
The Data-Driven Newsvendor Problem: New Bounds and Insights I: The SAA Order Is ε-Optimal with Probability at Least 1 − 2exp(−Nε²min(b,h)/((18 + 8ε)(b + h)))Research Paper
The newsvendor problem is the basic model of stocking under uncertain demand: an order quantity is fixed before a random demand is observed, and every unit short or left over is penalized. Its solution is a quantile of the demand distribution. In practice that distribution is unknown and only a sample of past demands is available. The standard remedy, sample…
Factoring Polynomials with Rational Coefficients III: A Reduced Basis of the Lattice of Multiples of h mod p^k Finds the Irreducible Factor h₀ = gcd(b₁, …, b_t)Research Paper
Factoring a polynomial with rational coefficients into irreducible factors is one of the basic tasks of computer algebra. Before 1982 the standard method (Berlekamp's algorithm modulo a small prime, Hensel lifting, then recombination of the p-adic factors, as in Zassenhaus's approach) could take exponential time, because the number of ways to recombine…
Factoring Polynomials with Rational Coefficients I: A Reduced Lattice Basis Satisfies |b_j|² ≤ 2^{n−1}·max|x_i|² for Any t Linearly Independent Lattice VectorsResearch Paper
A lattice in Rn is the set of integer combinations of n linearly independent vectors. Many problems in algorithmic number theory, cryptography and integer programming reduce to finding a short nonzero vector of a lattice, or a few short independent ones. Finding the shortest vector exactly is hard, but in 1982 A. K. Lenstra, H. W. Lenstra, Jr. and…
Existence of Correlated Equilibria III: A Game with Compact Hausdorff Strategy Spaces and Continuous Payoffs Has a Countably Additive Correlated EquilibriumResearch Paper
A correlated equilibrium (Aumann 1974) describes play in a game where a mediator draws a profile of recommended actions from a joint distribution and tells each player only that player's own recommendation; the distribution is an equilibrium when no player gains, on average, by departing from the recommendation. Correlated equilibria are the natural outcome…
Contact Interactions on a Lattice I: A Contact Process with (2d − 1)λₖ < kμ Dies Out from Every Finite Initial SetResearch Paper
The contact process is the basic model of an infection spreading on a lattice: each infected site recovers at a constant rate, and each healthy site becomes infected at a rate that depends on how many of its neighbours are infected. It was introduced by T. E. Harris in Contact Interactions on a Lattice (Ann. Probab. 2, 1974), and it became one of the…
Heavy-Traffic Limits for Queues with Many Exponential Servers: The Scaled Stationary M/M/n Queue Length Converges to a Hybrid Exponential–Normal LawResearch Paper
Telephone exchanges, call centers, hospital wards and cloud server pools are queues with a large number s of parallel servers. For such systems two classical approximations pull in opposite directions. Holding s fixed and letting the traffic intensity ρ→1 gives the conventional heavy-traffic limit, in which almost every customer waits. Letting s grow…
Packet Routing and Job-Shop Scheduling in O(Congestion + Dilation) Steps: Edge-Simple Paths with Congestion c and Dilation d Admit an O(c + d)-Step Schedule with Constant-Size QueuesResearch Paper
In a store-and-forward network, messages are cut into packets that travel from node to node along wires, one wire per time step, and wait in buffers between moves. Routing such traffic splits into two problems: choosing a path for each packet, and scheduling the packets along their paths, deciding at every step which packets move and which wait. Leighton,…
Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints 1: The Series-Parallel Algorithm Returns an Optimal SequenceResearch Paper
Sequencing jobs on one machine to minimize the total weighted completion time∑jwjCj is one of the basic problems of scheduling theory. Without precedence constraints it is solved by Smith's ratio rule (1956): sequence the jobs in nonincreasing order of wj/pj. With arbitrary precedence constraints the problem is NP-hard, as Lawler shows in the same…
Subadditive Ergodic Theory 6: The Ulam–Hammersley Constant of the Longest Increasing Subsequence Satisfies (8/π)^{1/2} ≤ c ≤ δ^{1/2} + δ^{−1/2}Research Paper
Ulam asked, in the early 1960s, how long the longest increasing subsequence of a random permutation typically is. The question is a test case for a whole class of problems in combinatorial probability: a quantity defined by an optimisation over exponentially many configurations (here, all subsequences) whose typical size has to be found without enumerating…
Subadditive Ergodic Theory 1: Kingman's Theorem — x₀ₜ/t Converges with Probability One and in Mean to a Finite ξ with E(ξ) = γResearch Paper
Many stochastic systems have an accumulated cost or passage time that grows with the length of an observation window. Splitting a window at an intermediate time gives an upper bound on the total, even when it does not give an equality. First-passage percolation and products of random matrices are examples discussed by Kingman (1973). A central question is…
Flowshop and Jobshop Schedules: Complexity and Approximation 2: The 3-Partition Flow Shop on Three Machines Has a Preemptive Schedule of Finish Time 2tB Iff a 3-Partition ExistsResearch Paper
A flow shop is the simplest multi-stage production model: every job passes through the same machines in the same order, and the question is how to sequence the work so that everything is finished as early as possible. Gonzalez and Sahni's 1978 paper in Operations Research settled the computational complexity of the preemptive version of this problem, in…
On the Generalized “Birth-and-Death” Process 1: For Rates λ(t), μ(t) ≥ 0 the Population Size Is Geometric with a Modified Zero Term, ξ_t = 1 − e^{−ρ}/W, η_t = 1 − 1/WResearch Paper
Population models often allow each individual to produce a new individual or die at rates that change over time. Seasonal conditions, exposure to an epidemic, and changing conditions in a laboratory population all make a constant rate a restrictive assumption. In Kendall's 1948 paper, the question is how the entire distribution of the population size…