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.
Learning to Predict by the Methods of Temporal Differences: Linear TD(0) Converges in Expected Value to the Ideal Predictions on Absorbing Markov ChainsResearch Paper
Temporal-difference (TD) methods learn to predict an eventual outcome from the differences between successive predictions rather than from the difference between each prediction and the final outcome. Sutton's 1988 paper Learning to predict by the methods of temporal differences introduced the TD(λ) family and gave the first convergence proof for a TD…
Data-Driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations II: Worst-Case Distributions from a Finite Convex ProgramResearch Paper
In data-driven stochastic optimization a decision maker knows the distribution of an uncertain parameter ξ only through N samples ξ^1,…,ξ^N. Wasserstein distributionally robust optimization hedges against this ignorance by evaluating a loss ℓ under the worst distribution in a ball, measured in the Wasserstein metric, around the…
Perfect Equilibrium in a Bargaining Model: The Perfect Equilibrium Partitions Are the Nonempty Closed Intervals A = Δ₁ and B = Δ₂ = A − εResearch Paper
Alternating-offer bargaining asks how an agreement is selected when two people can keep making proposals until one accepts. A prediction based only on behavior at the start may rely on threats that would no longer be sensible after a rejection. Ariel Rubinstein's 1982 paper studies strategies after every possible sequence of offers and gives a…
Data-Driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations I: Wasserstein Worst-Case Expectations as Finite Convex ProgramsResearch Paper
A decision maker who must minimize an expected cost EP[h(x,ξ)] rarely knows the distribution P of the uncertain parameter ξ; usually only N samples ξ^1,…,ξ^N are available. Replacing P by the empirical distribution (sample average approximation) tends to produce decisions that perform poorly out of…
On the Convergence of Stochastic Dual Dynamic Programming and Related Methods: DOASA Reaches an Optimal Policy in Finitely Many Iterations Almost SurelyResearch Paper
Stochastic dual dynamic programming (SDDP), introduced by Pereira and Pinto in 1991, is the standard method for multistage stochastic linear programs with many stages, such as hydro-thermal scheduling and long-term energy planning. It approximates each stage's expected future cost from below by the maximum of finitely many linear functions (cuts), built…
Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions 2: Geometric Convergence Rate of the Random Directions Algorithm to UniformResearch Paper
Generating points uniformly distributed over a bounded region S⊆Rn is a basic subroutine in Monte Carlo integration, in estimating the volume of a region, in randomized search for optimization, and in identifying redundant constraints of mathematical programs. When S is given only implicitly, for instance by a system of inequalities, the…
Poisson Approximation for Dependent Trials 2: For φ-Mixing Bernoulli Trials, an Order-λ⁻¹ Bound on |Eh(W) − 𝒫_λh| in Var W − λ + 2(2m+1)Σp_i² and nφ(m+1)Research Paper
The number of successes in many rare trials is approximately Poisson. For independent trials the
quality of that approximation was quantified by Le Cam in 1960: if X1,…,Xn are independent
Bernoulli variables with P(Xi=1)=pi, W=∑iXi and λ=∑ipi, the total variation
distance between the law of W and the Poisson law with mean λ is…
Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions 1: Symmetric Mixing Algorithms Converge to the Uniform Distribution from Every Starting PointResearch Paper
Sampling uniformly from a bounded region can be difficult when direct transformation of a familiar random variable is unavailable and rejection sampling spends most of its trials outside the region. Robert L. Smith studied procedures that move within the region: from the current point, choose a direction, form the line set through that point inside the…
On the Convergence of Interior-Reflective Newton Methods for Nonlinear Minimization Subject to Bounds 1: The Interior-Reflective Line Search Algorithm Drives D_k²g_k to ZeroResearch Paper
Minimizing a smooth function subject to simple bounds on the variables, l≤x≤u, is one of the most common problems in nonlinear optimization: it arises on its own (nonnegativity constraints, box-constrained least squares, parameter estimation with physical ranges) and as the subproblem of augmented Lagrangian and penalty methods. The classical…
Optimal Auction Design: Giving the Object to a Bidder with the Highest Priority Level c̄ᵢ(tᵢ) ≥ t₀ and Charging (6.8) Is an Optimal Auction MechanismResearch Paper
A seller with one indivisible object must decide whether to keep it or transfer it to one of several bidders whose values she does not observe. The allocation and the payment rule affect what bidders choose to report. Myerson's 1981 paper identifies a revenue-maximizing rule when bidders' private value estimates are independent, their densities are…
Poisson Approximation for Dependent Trials 3: For Independent Trials with max p_i ≤ λ/2, |Eh(W) − 𝒫_λh + (Σp_i²)𝒫_λU_λh| ≤ (24 + 96√2)λ⁻¹Σp_i³Research Paper
The number of successes in many rare, roughly independent trials is approximately Poisson. This law of small numbers is used for counts of rare events in reliability, insurance, epidemiology, queueing and random combinatorics. A quantitative version says how large the error is. For independent Bernoulli trials with success probabilities p1,…,pn and …
The Complexity of Markov Decision Processes IV: In a Deterministic Process a Cheapest T-Arc Walk Is a Walk of Fewer Than n³ Arcs Plus One Repeated CycleResearch Paper
Finite-horizon Markov decision processes ask which decisions minimize accumulated cost over a specified number of stages. In a stationary process, the same costs and transitions apply at every stage. This compact input can describe a horizon T much larger than the state set, so a method that processes all T stages one by one may take time exponential in the…
The Bargaining Problem: The Nash Product Maximizer Is the Unique Solution Satisfying Invariance, Symmetry, IIA and Pareto EfficiencyResearch Paper
Two parties who can cooperate for mutual benefit must still agree on how to share the benefit. In
The Bargaining Problem (Econometrica, 1950) John Nash asked which agreement two rational
bargainers of equal skill should reach. His answer is not a model of haggling: it is a list of
conditions any reasonable rule should satisfy, together with a proof that…
An Optimal Algorithm for On-line Bipartite Matching 2: No Randomized On-line Algorithm Guarantees an Expected Matching Larger Than n(1 − 1/e) + o(n)Research Paper
An online matching algorithm must commit to each assignment when a request arrives, before it sees later requests. This limitation arises whenever waiting for the full instance is impossible: an available resource can be assigned to a current request or saved for an unknown future request. The quality of the assignment is measured by how many requests can…
Wait-and-Judge Scenario Optimization 2: Over Generic Sets, P^N{V(x_N) > ε(s_N)} ≤ γ*, the Least ξ(1) over Degree-N Polynomials Feasible for (31)Research Paper
A solution of a scenario optimization program is chosen after observing finitely many uncertain constraints. Its future reliability depends on constraints that were not sampled. The usual advance question asks how many samples are needed to make every output reliable. Campi and Garatti instead ask what can be certified after solving the program, when the…
Supply Chain Coordination with Contracts VI: With a Forecast Update, Buy-Back Terms with w₁ − w₂ + λc₂ = λc₁ Give the Retailer λΩ₁(q₁) and a Lower Period-2 Margin w₂ − c₂ < w₁ − c₁Textbook
A newsvendor retailer who may order twice faces a tradeoff. Ordering late lets the retailer use a better demand forecast. Ordering early lets the supplier produce more cheaply, with longer procurement lead times and no overtime labor. Fisher and Raman (1996) document such forecast improvements between ordering epochs in fashion apparel. A decentralized…
Integer Programming with a Fixed Number of Variables 1: If B(p,r) ⊂ τK ⊂ B(p,R) with R/r ≤ c₁ and τK Misses the Lattice, Fewer Than 1 + c₁c₂√n Lattice Hyperplanes H + kbₙ Meet B(p,R)Research Paper
The integer linear programming feasibility problem asks, for an integer m×n matrix A and b∈Zm, whether some x∈Zn satisfies Ax≤b. It is NP-complete, so no algorithm polynomial in the length of the data is expected. H. W. Lenstra, Jr. (Math. Oper. Res. 8 (1983) 538–548) showed that the picture changes when the number of…
Supply Chain Coordination with Contracts VII: In the Single-Location Base-Stock Model the Transfers t_I = (1 − λ)h_r, t_B = β_r − λβ Make the Retailer's Cost λc(s_r)Textbook
A retailer can keep too little inventory even when its own stocking decision is optimal. In the single-location model of Cachon, Supply Chain Coordination with Contracts (2003), the supplier suffers a cost when the retailer has backorders, but the retailer does not bear that part of the cost. The supplier and retailer therefore prefer different base-stock…
On Linear Characterizations of Combinatorial Optimization Problems III: Zero-One and Integer-Programming-Type Problems Have Small Facial DescriptionsResearch Paper
Many discrete optimization problems can be described by linear inequalities, even when their feasible solutions are integer vectors. A linear description lets one study the geometry of the feasible set and connect combinatorial methods with linear programming. The number of inequalities may be large, so a more basic question is whether each inequality needs…
Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments VI: Revenue-Ordered Offer Sets Grow with Capacity Left and Shrink with Time LeftResearch Paper
In airline and hotel revenue management a firm sells a fixed stock of a perishable resource (seats on a flight leg, rooms on a night) over a finite selling horizon, and in each period decides which fare classes to open. Customers do not buy a fixed fare: they choose among the fares on offer, or leave. Talluri and van Ryzin (Management Science, 2004)…
Supply Chain Coordination with Contracts II: With Price-Dependent Demand the Price-Contingent Buy-Back Gives the Retailer λΠ(q, p), as Revenue Sharing Does, and Coordinates Price and QuantityTextbook
A retailer who controls both inventory and price can respond to a supply contract in two ways. A contract that induces the right order quantity at a fixed price may change the retailer's incentive to raise or lower that price. For a one-season supply chain, Cachon's chapter compares familiar contracts under price-dependent demand and identifies a…
Send-and-Split Method for Minimum-Concave-Cost Network Flows I: A Minimum-Cost Flow Exists iff Every Simple Circulation Has Nonnegative Cost, and Then an Extreme One Exists (Theorem 1)Research Paper
Many network design and production–distribution problems have economies of scale: shipping twice as much along an arc costs less than twice as much, because of fixed charges, set-up costs or volume discounts. Modelled as network flows, such problems ask for a flow of least cost when each arc cost is a concave function of the flow on the arc. Classical…
Finding Minimum-Cost Circulations by Successive Approximation II: For Real Costs, the Strongly Polynomial Loop Reaches a Minimum-Cost Circulation After at Most m⌈log₂(2n)⌉ RefinementsResearch Paper
A minimum-cost circulation is a way to send flow around a directed network while respecting capacities and paying a cost per unit on each arc. It is a basic form of network optimization: a minimum-cost flow with prescribed supplies and demands can be reduced to a circulation problem, and the circulation formulation exposes the residual arcs on which a flow…
Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach 1: The f-Divergence Robust Mean Is the Sample Mean plus √(ρ·s_n²/n) up to o(n^(−1/2)) Almost SurelyResearch Paper
Distributionally robust optimization replaces the average of a loss over a sample by its worst-case average over all distributions close to the sample. When closeness is measured by an f-divergence, the worst case over a ball of radius ρ/n around the empirical distribution is also the upper endpoint of a generalized empirical likelihood confidence…
Online Stochastic Matching: Beating 1-1/e 3: No Online Algorithm Beats Expected Approximation Factor 26/27 on a 6-Cycle, and None Reaches 1 − o(1) on Disjoint 6-CyclesResearch Paper
Online bipartite matching asks an algorithm to assign arriving requests to resources it cannot reassign later. In display advertising, the requests are page views (impressions) and the resources are advertisers who have bought a fixed number of impressions in advance; each impression must be served immediately or lost. In the adversarial model, Karp,…