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.
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…
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…
Loss Networks 3: If E e^{λX} < ∞ and 2E(X − C)⁺ < E(C − X)⁺, i.i.d. Loads on the Complete Graph Fit on Direct and Two-Edge Routes with Probability → 1Research Paper
Telephone and data networks are often fully connected at the core: every pair of switching centres has a direct trunk group, and a call that finds its direct trunk full may be alternatively routed over a two-link path through a third, tandem centre. Whether such a network can absorb fluctuations of demand without losing traffic depends on how the spare…
Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem 1: The Spanning-Tree Interchange Tour ψ* Is a Minimal Cost TourResearch Paper
The traveling salesman problem is NP-hard in general, so special cost structures under which it can be solved exactly in polynomial time are of lasting interest in combinatorial optimization and scheduling. One of the earliest and most cited such cases comes from sequencing on a machine whose condition is described by a single real number: a furnace…
On Tail Probabilities for Martingales 3: If E exp[−e(λ)W] ≤ e^{−λa} and E exp[−f(λ)W] ≥ e^{−λ(a+1)} for All λ ≥ 0, Then P{W < b} > ½ exp[−(½ + 2δ)a²/b]Research Paper
Freedman's inequality bounds the probability that a martingale with increments bounded above by 1 reaches a level a before its accumulated conditional variance exceeds b: the bound is exp[−a2/2(a+b)] (D. A. Freedman, On Tail Probabilities for Martingales, Ann. Probab. 3 (1975) 100–118, Theorem (4.1), doi:10.1214/aop/1176996452). It is the standard tool…
The Polynomial Hierarchy and a Simple Model for Competitive Analysis: Every Optimum of the (p+1)-Level Linear Game J'(F) Is Binary, with x(F) = 1 iff the Σ_p Sentence (3.3) HoldsResearch Paper
Multi-level programs model a hierarchy of decision makers: a leader commits to a decision, a follower optimises given it, a follower of the follower optimises given both, and so on. Bilevel programs are the standard model of Stackelberg competition, toll setting, network interdiction and many other leader–follower problems in operations research (Candler…
A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite Element Approximation 1: For 0 < ρ < 2r, the Modified Dual Algorithm Converges Strongly to (v*, Av*)Research Paper
Many problems in mechanics and optimal control are posed as the minimization of a convex functional of the form f(Av)−⟨b,v⟩, where A is a differential operator and f is non-smooth: an obstacle, a friction term, a plasticity threshold. Splitting the variable, y=Av, separates the linear operator from the non-smooth function, and a Lagrange…
Shock Models and Wear Processes III: The First Passage Time of a Nondecreasing Markov Wear Process Above a Fixed Level Has an IHRA DistributionResearch Paper
Reliability theory classifies life distributions by how they age. A device whose failure rate tends to increase over time is "wearing out", and the class of distributions with increasing hazard rate average (IHRA) is the one that is closed under forming coherent systems of independent components (Birnbaum, Esary and Marshall, 1966). This makes IHRA the…
Shock Models and Wear Processes IV: With a Random Threshold, Shock Survival Probabilities Are Submultiplicative for Every Damage Law Iff the Threshold Is NBUResearch Paper
Reliability theory classifies life distributions by how they age. A device whose remaining life, once it has survived to age t, is stochastically shorter than the life of a new device is called new better than used (NBU). The NBU class, together with the classes IHR (increasing hazard rate) and IHRA (increasing hazard rate average), organizes much of the…
Linear Programming and Markov Decision Chains 3: The Representative of a Pure Stationary Policy Is an Extreme Point of the Dual LPResearch Paper
A Markov decision chain is a controlled Markov chain: in each state the controller picks an action, collects a reward and moves to a random next state with probabilities that depend on the state and the action. Under the average reward criterion, the long-run reward per step, an optimal policy can be computed by linear programming. For chains in which every…
Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model: The Discrete-Time Proximity Process Is Dual to the Branching Process with InterferenceResearch Paper
Many models in probability, statistical physics and the theory of stochastic networks are interacting particle systems: infinitely many sites, each in state 0 or 1, each updating at random according to the states of a few other sites. A basic question about such a system is ergodicity: does it have a unique stationary distribution, and does its law converge…
The Relation between Customer and Time Averages in Queues: H = λG on Every Sample Path When 0 < λ < ∞, G < ∞ and Each f_n Vanishes Outside [t_n, t_n + s_n] with s_n/n → 0Research Paper
Little's law L=λW says that the long-run average number of customers in a system equals the arrival rate times the average time a customer spends there. It is one of the most used identities in queueing theory, and it holds on individual sample paths under weak conditions (Little 1961; Stidham 1974). Many quantities of interest are not head counts,…
Globally Convergent Inexact Newton Methods I: Inexact Newton Backtracking Converges to Every Limit Point Where F′ Is Invertible, That Point Is a Zero of F, and Initial Steps Are Eventually AcceptedResearch Paper
Newton's method for a nonlinear system F(x)=0, with F:Rn→Rn, solves the linear system F′(xk)sk=−F(xk) at every step. For large systems that solve is itself iterative (a Krylov method such as GMRES), and it is stopped early. The resulting inexact Newton methods, introduced by Dembo, Eisenstat and Steihaug (SIAM J. Numer. Anal. 19…
Shock Models and Wear Processes I: Under Poisson Shocks, Cumulative Nonnegative I.I.D. Damage up to a Fixed Threshold Gives an IHRA Life DistributionResearch Paper
Reliability theory classifies life distributions by how they age. The IHRA class (increasing hazard rate average) is the smallest class of life distributions that contains the exponential distributions and is closed under forming coherent systems and taking limits in distribution (Birnbaum, Esary and Marshall 1966). It is therefore the natural class for the…
Reflected Brownian Motion on an Orthant: The Skorokhod Construction Yields an Adapted, Almost Surely Unique, Time-Homogeneous Markov ProcessResearch Paper
Reflected Brownian motion on the orthant is the diffusion that arises as the heavy-traffic limit of open networks of queues. In a K-station network the scaled queue-length vector lives in the nonnegative orthant R+K; in the interior it moves like a Brownian motion, and when a station empties the process is pushed back into the orthant in a…
Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach 3: Robust Optimal Values and Solution Sets over f-Divergence Balls Are ConsistentResearch Paper
Stochastic optimization asks for a decision x in a set X⊂Rd that minimises an expected loss EP0[ℓ(x;ξ)] when the distribution P0 of the data ξ is known only through a sample ξ1,…,ξn. The classical estimator, sample average approximation, replaces P0 by the empirical distribution Pn. Distributionally…
Deterministic Equivalents for Optimizing and Satisficing under Chance Constraints 1: Under Normality, the E-Model Chance Constraints Are Equivalent to the Convex Program (29)Research Paper
Chance-constrained programming replaces a linear program maxc′x subject to Ax≤b by a problem in which some data are random and each constraint only has to hold with a prescribed probability. Charnes and Cooper introduced the idea in 1959 for scheduling heating-oil production against weather-dependent demand, and the formulation is now a standard…
On Representatives of Subsets: Two Partitions into m Classes Have a Common System of Representatives When Any k Classes of One Meet at Least k Classes of the OtherResearch Paper
Many assignment questions reduce to one combinatorial question: given finitely many sets, can one choose a different element from each? Workers are matched to jobs they are qualified for, rows of a matrix to columns with nonzero entries. The criterion for when this is possible is Hall's marriage theorem, first stated and proved by P. Hall in a five-page…
Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey 2: The Optimal Preemptive Open Shop Makespan Equals the Largest Machine Load or Job LengthResearch Paper
Open shops model production and service systems in which every job must visit every machine, but the order of the visits is free: a car that needs an inspection, a wash and a tyre change, a patient who needs several tests, a student who sits several exams. The survey of Graham, Lawler, Lenstra and Rinnooy Kan (Ann. Discrete Math. 5, 1979) fixed the…
Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey 1: The Optimal Two-Machine Open Shop Makespan Is max{T₁, T₂, maxⱼ(aⱼ + bⱼ)}Research Paper
Shop scheduling asks how to sequence jobs that each need processing on several machines. In an open shop, a job's operations may be executed in any order, as in testing stations, repair bays, or classroom and examination timetables, where the order in which a candidate visits the stations is irrelevant. The objective studied here is the makespanCmax,…
Extensions of the Queueing Relations L = λW and H = λG: Under (14) and (15) the Time Average H(t) Converges if and only if the Customer Average G(s) Does, and Then H = λGResearch Paper
Queueing results often relate an average accumulated over customers to an average accumulated over time. In the familiar relation L=λW, the long-run average number in a system equals the arrival rate times the average time spent there. Glynn and Whitt study a broader relation, H=λG, that can represent queue lengths and waiting times but also…
A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management 2: Frequent Re-solving Loses at Most O(√T) Against the Deterministic LP, Uniformly in the CapacitiesResearch Paper
Network revenue management is the problem of selling several limited, perishable resources (seats on flight legs, hotel room-nights, machine hours) to customers who arrive over time and each want a fixed bundle of them. A seller who accepts every request early may run out of the resources that the most valuable later customers need, and a seller who is too…