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.
Optimal Pricing and Return Policies for Perishable Commodities I: Unlimited Returns at Partial Credit Coordinate the Channel for Every Demand DistributionResearch Paper
A manufacturer of a perishable good (newspapers, magazines, bread, seasonal fashion, printed books) sells through a retailer who must commit to an order before demand is known. Unsold units lose most of their value; unmet demand costs goodwill. When the retailer alone bears the risk of leftovers, it orders less than an integrated firm would, and the channel…
A New Class of Random Number Generators 1: For Prime m = bʳ + bˢ − 1, Every Nontrivial Add-with-Carry Sequence Is Periodic After r Steps, with Period the Order of b mod mResearch Paper
Simulation, Monte Carlo integration and randomized algorithms consume long streams of numbers that should behave like independent uniform draws. A deterministic generator with finite state is eventually periodic, so its period is the first figure of merit: a stream cannot be longer than its cycle. G. Marsaglia and A. Zaman, A new class of random number…
A Proof of the Optimality of the Shortest Remaining Processing Time Discipline: SRPT Minimizes the Number of Jobs in System at Every Time, for Every Arrival Stream and Every ScheduleResearch Paper
A single processor receives jobs over time, each with a known amount of work, and may interrupt a job at any moment to work on another. Which rule should decide what to process? For the number of jobs waiting or in service, the answer is the Shortest Remaining Processing Time (SRPT) rule: at every moment, work on the job in system that is closest to…
Values of Large Games II: Oceanic Games 1: Closed-Form Values of Interior Oceanic GamesResearch Paper
Weighted voting bodies often combine a few large blocs with a mass of small, unorganized voters: shareholders' meetings with a handful of large holders and a dispersed float, legislatures with party blocs and independents. The Shapley value measures each participant's voting power as the probability of being pivotal — the one whose arrival first turns a…
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…
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…
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…
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 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…
Linear Programming and Finite Markovian Control Problems VII: Bias Optimality — Four Equivalent Characterizations of a Bias Optimal Pure Stationary PolicyTextbook
A finite Markov decision problem can have several policies with the same long-run average reward even though they behave differently before reaching a recurrent class. Average reward discards a finite initial advantage: dividing total reward by the horizon sends any fixed transient contribution to zero. In applications where the process runs for a long but…