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.
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…
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…
On the Relation Between Integer and Noninteger Solutions to Linear Programs: Deep in the Optimal-Basis Cone, z₂(b) = z₁(b) + φ(b) and the Group Problem Gives an Integer OptimumResearch Paper
An integer program is a linear program whose variables must take integer values. Its linear relaxation can be solved efficiently, while the integer program itself is NP-hard in general, so a recurring question in integer programming is how much the optimal solution of the relaxation says about the integer optimum. Simple rounding of the fractional optimum…
Residual Life Time at Great Age 1: Every Nondegenerate Limit Law of the Normed Residual Life Time Is of Type Π, Π_γ, Γ_α or Γ_{γ,α}Research Paper
A component with a random lifetime X that has survived to age t still has a random residual life timeX−t. Reliability engineering, actuarial science and the statistics of exceedances over high thresholds all ask how the conditional law of X−t given X>t behaves when the age t is large. If X is exponential, the residual life has the same law at every…
Simulation Output Analysis Using Standardized Time Series 1: For Every g in the Class 𝓜, (Ȳₙ(1) − μ)/g(Ȳₙ) ⇒ B(1)/g(B) Under the FCLT (2.1)Research Paper
A discrete-event simulation of a queue, an inventory system or a communication network produces an output process Y={Y(t):t≥0}, and the quantity of interest is usually its steady-state meanμ, the long-run average of Y. The natural estimator is the time average Yˉn(1)=n1∫0nY(s)ds of a run of length n. A confidence interval…
A Suggested Computation for Maximal Multi-Commodity Network Flows: With Nonnegative Simplex Multipliers, Shortest-Chain Labels Prove the Arc-Chain Basis Optimal or Find an Entering ChainResearch Paper
The maximal multi-commodity flow problem asks how much total flow several commodities, each travelling from its own sources to its own sinks, can send through a network whose arcs have shared capacities. It arises in communication and transportation planning: Kalaba and Juncosa's 1956 study of communication networks (Management Science 3(1)) leads to linear…
A Variational Inequality Formulation of the Dynamic Network User Equilibrium Problem II: Under Linear Arc Delay αx(t) + β the Arc Exit Time Is Strictly Increasing (FIFO Holds)Research Paper
Dynamic traffic assignment models how commuters choose routes and departure times when travel times change over the day. In the model of Friesz, Bernstein, Smith, Tobin and Wie (Oper. Res. 41 (1993)), the time to traverse a path is built recursively from arc exit-time functions: a vehicle that enters an arc at time t leaves it at time τ(t). The…
Data-Driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations III: Asymptotic Consistency of Wasserstein Robust SolutionsResearch Paper
Many decisions in operations research and machine learning minimize an expected cost EP[h(x,ξ)] whose distribution P is unknown and is seen only through N independent samples. The sample-average approximation replaces P by the empirical distribution and is known to produce decisions with poor out-of-sample performance when N is small. Distributi…