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.
Exponential Lower Bounds for Polytopes in Combinatorial Optimization: The TSP Polytope Has Extension Complexity 2^Ω(√n)Research Paper
Combinatorial optimization problems are routinely solved by writing the convex hull of their feasible solutions as the feasible region of a linear program. When that convex hull has exponentially many facets, a classical trick is to add auxiliary variables: a polytope with many facets may be the linear projection of a higher-dimensional polyhedron with few.…
A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in O(n log n) or O(n) Time: Minimal Optimal Predecessor Lists Are Characterized by Strictly Increasing BreakpointsResearch Paper
The dynamic lot size model asks when, and how much, to order of a single item over a planning horizon of n periods with known, time-varying demands, setup costs, unit order costs and holding costs. It is the textbook model of production planning and the building block of material requirements planning, multi-item scheduling and many decomposition schemes…
An Efficient Algorithm for Computing an Optimal (r, Q) Policy in Continuous Review Stochastic Inventory Systems: Algorithm OPT Returns an Optimal Reorder Point and Order QuantityResearch Paper
(r, Q) policies are the standard replenishment rule for a single item under continuous review: whenever the inventory position (stock on hand plus on order minus backorders) drops to the reorder pointr, an order of size Q is placed. They are known to be optimal in the classical models with Poisson or compound renewal demand, constant or exogenous lead…
Multi-parameter Mechanism Design and Sequential Posted Pricing 3: Order-Oblivious Posted Prices 2-Approximate the Optimal Revenue under a Uniform Matroid ConstraintResearch Paper
Myerson's optimal auction (Myerson 1981) maximizes a seller's expected revenue when buyers have independent private values, but it is a sealed-bid mechanism: every buyer reports a value, and the allocation and payments are computed from all reports at once. Real sellers more often post prices: buyers arrive, each sees a take-it-or-leave-it price, and buys…
Project Scheduling with Time Windows and Scarce Resources VIII: A Vertex Schedule Maximizes the Net Present Value iff Its Spanning-Tree Subprojects Have the Right SignsTextbook
Long-running projects such as construction, plant engineering or software development involve payments to and from the contractor at many points in time: disbursements when activities are carried out, progress payments when milestones are reached. When the planning horizon is long, money received later is worth less, and the natural financial objective is…
One-Machine Sequencing to Minimize Certain Functions of Job Tardiness I: SPT Order Minimizes Total Tardiness When Each Due Date Plus Processing Time Is at Most the Next SPT Completion TimeResearch Paper
A shop that promises delivery dates is judged by how late its orders are, not by how early. For a single machine processing n jobs that are all available at time 0, the total tardiness of a processing order,
On the Variational Principle II: Under Linearly Independent Active Constraint Gradients, a Bounded-Below Problem Has ε²-Optimal Feasible Points Satisfying the Lagrange Multiplier Rule up to εResearch Paper
The classical Lagrange multiplier rule and its inequality-constrained form, the Karush–Kuhn–Tucker (KKT) conditions, are necessary conditions satisfied at a minimizer of a constrained problem. In finite dimensions, a continuous function bounded below on a closed bounded feasible set attains its minimum, so the rule describes an actual point. In an…
On the Variational Principle I: Near Every ε-Minimizer of a Lower Semicontinuous Function Bounded Below on a Complete Metric Space Lies a Strict Minimizer of F + (ε/λ)d(v, ·)Research Paper
A function that is bounded below need not attain its infimum: ex on R has infimum 0 and no minimizer. The classical "variational principle" says that at a minimizer uˉ of a differentiable functional, F′(uˉ)=0. Without compactness there may be no minimizer, and the principle has nothing to say. In 1974 Ivar Ekeland showed that a weaker…
Dimensioning Large Call Centers I: The Rationalized Staffing Function Is Asymptotically OptimalResearch Paper
A call center with N agents facing Poisson arrivals at rate λ and exponential service at rate μ is the M/M/N (Erlang-C) queue. Choosing N trades the cost of agents against the cost of customers waiting, and in practice it is done with the square-root safety-staffing ruleN≈R+yR, where R=λ/μ is the offered load. Borst,…
Fundamentals of Queueing Theory IX: Kingman's Upper Bound on the G/G/1 Queue WaitTextbook
The single-server queue with general independent interarrival and service times, the G/G/1 queue, is the basic model of a congested resource: a machine, a link, a checkout. For Markovian arrivals or services the mean wait has a closed form (the Pollaczek–Khintchine formula for M/G/1, the geometric law for G/M/1). For general distributions it has none, and…
A Multicut Algorithm for Two-Stage Stochastic Linear Programs 2: Multicut for Simple Recourse Stops Within J·m2 + 1 IterationsResearch Paper
Two-stage stochastic linear programs model decisions taken before uncertainty is resolved (first stage) and corrected afterwards at a cost (second stage, the recourse). The standard solution method for problems with finitely many scenarios is the L-shaped method of Van Slyke and Wets (1969), an outer linearization in the style of Benders decomposition: a…
The Price of Anarchy of Finite Congestion Games IV: For Symmetric Games the Maximum Social Cost Price of Anarchy Is at Most 5/2Research Paper
The price of anarchy measures how much a system of selfish agents loses compared with a centrally optimized one: it is the worst ratio, over all Nash equilibria, between the social cost of the equilibrium and the optimal social cost. Koutsoupias and Papadimitriou introduced it in 1999 (Worst-case equilibria, STACS 1999), and bounding it for routing and…
The Price of Anarchy of Finite Congestion Games I: The Pure Price of Anarchy of the Average Social Cost Is 5/2Research Paper
When many independent users share a resource whose cost grows with use (links of a network, servers, machines), each user chooses for itself, and the outcome is a Nash equilibrium rather than a socially optimal allocation. The price of anarchy, introduced by Koutsoupias and Papadimitriou (STACS 1999), measures the cost of this decentralisation: the worst…
The Dantzig Selector: Statistical Estimation When p Is Much Larger than n 1: ℓ2 Error Bound for Sparse Parameters under the Uniform Uncertainty PrincipleResearch Paper
In many statistical applications the number of unknown parameters p is far larger than the number of observations n: gene-expression studies with tens of samples and thousands of genes, imaging problems with fewer measurements than pixels, and nonparametric curve estimation from finitely many noisy samples. Least squares is useless in this regime, since the…
Reinforcement Learning: An Introduction XII: The Policy Gradient TheoremTextbook
Policy gradient methods learn a parameterized policy π(a∣s,θ) directly, by stochastic gradient ascent on a scalar performance measure J(θ), instead of deriving the policy from learned action values. They are how reinforcement learning handles continuous action spaces, stochastic optimal policies and prior knowledge built into the policy's…
A Multicut Algorithm for Two-Stage Stochastic Linear Programs 1: Worst-Case Bound on Multicut Major IterationsResearch Paper
Two-stage stochastic linear programs with recourse are a standard model for planning under uncertainty: a first-stage decision x is taken before a random outcome ξ is observed, and a second-stage (recourse) decision y corrects for it afterwards at a cost. When ξ has finitely many realizations, the problem is a large but structured linear program, and…
On the Power of Randomization in On-Line Algorithms 4: Restarting a Bounded-Cost Algorithm Is (1+ε)α-Competitive in Games of Finite DiameterResearch Paper
Competitive analysis compares an online algorithm, which must answer each request before seeing the next, with the optimal off-line solution of the same request sequence. Ben-David, Borodin, Karp, Tardos and Wigderson (Algorithmica 11, 1994) set up a general framework, request-answer games, in which paging, the K-server problem and metrical task systems are…
On the Power of Randomization in On-Line Algorithms 3: An Augmented Potential Function Yields an Explicit Deterministic α∘β-Competitive AlgorithmResearch Paper
Competitive analysis measures an online algorithm, which must answer each request before seeing the next, against the best off-line answer to the whole request sequence. Randomized online algorithms are often much better than deterministic ones against an oblivious adversary, who fixes the requests in advance; the paging problem is the standard example.…
Optimization of Multiclass Queueing Networks: Polyhedral and Nonlinear Characterizations of Achievable Performance II: An O(n²) Extended Formulation of the Multiclass M/M/1 Performance PolymatroidResearch Paper
A single server shared by several classes of customers is the basic model of scheduling under uncertainty: jobs of different types arrive at random, need random amounts of work, and a scheduler decides at every moment which type to serve. A classical way to optimize such a system, the achievable region approach, describes the set of all performance vectors…
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization 3: Fractional Double Greedy on the Multilinear Extension Achieves 1/2 of the OptimumResearch Paper
Unconstrained submodular maximization (USM) asks for a subset S of a finite ground set N maximizing a nonnegative submodular function f. It contains Max-Cut, Max-DiCut and maximum facility location as special cases, and it is the basic subproblem of many constrained submodular maximization algorithms. Because f is given only through a value oracle,…
On the Power of Randomization in On-Line Algorithms 1: α-Competitiveness Against Adaptive On-Line and β Against Oblivious Adversaries Give a Deterministic α∘β-Competitive AlgorithmResearch Paper
An online algorithm must answer each request before it sees the next one. Its performance is compared with an optimum that may choose all its answers after seeing the complete request string. Randomization can improve an online algorithm's guarantee when the request string is fixed in advance. The comparison changes when an adversary chooses later requests…
On the Power of Randomization in On-Line Algorithms 2: The Bound α∘β Against Adaptive Off-Line Adversaries Is TightResearch Paper
An on-line algorithm must answer each request as it arrives, without knowing the requests to come; paging, caching, the k-server problem and metrical task systems are standard examples. Its quality is measured by competitive analysis: its cost is compared with the cost of an optimal off-line solution that knows the whole request sequence. For randomized…
Gradient Convergence in Gradient Methods with Errors II: With Zero-Mean Stochastic Errors, Almost Surely Either f(x_t) → −∞ or f(x_t) Converges and ∇f(x_t) → 0Research Paper
Stochastic gradient methods minimize a function f when only noisy estimates of its gradient are available: each step moves along a descent direction corrupted by random noise. They are the standard training algorithm for neural networks and the basic tool of stochastic approximation, and the question every user faces is what can be guaranteed when f is nonco…
Reinforcement Learning: An Introduction VII: The Error Reduction Property of n-step ReturnsTextbook
Temporal-difference (TD) learning estimates the value of a policy by moving a current estimate toward a target built from observed rewards and from the estimate itself. Chapter 7 of Sutton and Barto's Reinforcement Learning: An Introduction (2nd ed., MIT Press, 2018) interpolates between the two extreme targets of the preceding chapters: the one-step TD…
How Much Data Is Sufficient to Learn High-Performing Algorithms? Generalization Guarantees for Data-Driven Algorithm Design 2: Neutral Affine Maximizers Have Pseudo-Dimension at Least ⌊n/2⌋Research Paper
In data-driven algorithm design, an algorithm or mechanism comes with a vector of tunable parameters ρ, and the parameters are chosen by optimizing average performance over sample instances drawn from an unknown distribution. How many samples suffice for the empirical optimum to be near-optimal in expectation is governed by the pseudo-dimension of the…