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.
An Overview of Pricing Models for Revenue Management: Performance Guarantee of the Deterministic Price Heuristic in Periodic-Review PricingResearch Paper
Dynamic pricing under limited inventory is a core problem of revenue management: a seller holds C0 units of a perishable product (airline seats, hotel rooms, seasonal goods) and must choose prices over a finite selling horizon while demand is random and responds to price. The exactly optimal policy solves a stochastic dynamic program whose state is the…
Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs: Binding Cuts Force Degenerate Descendant Problems in Nested DecompositionResearch Paper
Multistage stochastic linear programs model decisions taken in periods t=1,…,T while a random vector ξt is revealed period by period: production and capacity planning, energy scheduling, asset–liability management. With finitely many scenarios the problem is one very large linear program with a tree structure, and decomposition methods solve it…
Santa Claus Schedules Jobs on Unrelated Machines: The Configuration LP Has Integrality Gap at Most 33/17Research Paper
Scheduling jobs on unrelated machines so as to minimize the makespan (the time at which the last machine finishes) is one of the central problems of approximation algorithms. For the general problem, Lenstra, Shmoys and Tardos (1990) gave a 2-approximation and showed that no polynomial-time algorithm achieves a factor below 3/2 unless P = NP; closing the…
Processing Networks IX: Fluid Stability of the Proportionally Fair AllocationTextbook
Every control policy formalized so far in this series — HLSPS (mission VI), back-pressure/
max-weight (mission VIII) — allocates service effort to entire job classes as indivisible units.
Proportional fairness takes a different starting point: it is a general-purpose recipe for
dividing a shared, continuously divisible resource among competing demands,…
The Assignment Game I: The Core 1: The Core Is the Set of Optimal Solutions of the Dual Assignment LPResearch Paper
A two-sided market in which each participant trades with at most one partner on the other side — houses and buyers, workers and firms, producers and consumers under exclusive bilateral contracts — is the setting of L. S. Shapley and M. Shubik's assignment game (Int. J. Game Theory 1 (1971) 111–130). Money is transferable, so the natural solution concept is…
Learnability, Stability and Uniform Convergence I: A Problem Is Learnable if and only if It Admits a Uniform-RO Stable Universal AERMResearch Paper
In supervised binary classification, a hypothesis class is learnable if and only if it has uniform convergence, meaning that empirical risks converge to true risks uniformly over the class. When that holds, empirical risk minimisation (ERM) learns. This equivalence, due to Vapnik and Chervonenkis and extended to real-valued losses by Alon, Ben-David,…
Processing Networks V: Lyapunov Stability Criteria for Fluid ModelsTextbook
Mission III's Theorem 6.2 reduces SPN stability to a question about deterministic fluid model
solutions: does every solution of a fixed system of equations get driven to the origin,
uniformly in its starting size? Mission IV showed how to derive the extra, policy-specific
equations a fluid model must satisfy. What remains is a method for proving that a…
On the Optimality of Generalized (s, S) Policies: A Generalized (s, S) Policy Is Optimal in Every Period of the Finite-Horizon Inventory ProblemResearch Paper
In a periodic-review inventory system a manager observes the stock level before ordering, decides how much to order, and then faces random demand. When ordering costs a fixed setup charge plus a constant price per unit, Scarf (1960) proved that an (s,S) policy is optimal in every period of a finite-horizon problem: order up to S when the stock falls below s,…
A Dynamical Approach to an Inertial Forward-Backward Algorithm for Convex Minimization: The IFB Iterates Minimize the Objective and Converge Weakly to a MinimizerResearch Paper
Many problems in signal processing, statistics and operations research ask to minimize a sum Θ=Φ+Ψ of a nonsmooth convex term Φ (a constraint indicator, an ℓ1 penalty) and a smooth term Ψ. The standard method is the forward-backward (proximal-gradient) algorithm: an explicit gradient step on Ψ followed by a proximal step on Φ.…
Three Partition Refinement Algorithms 1: Distinguishing-Prefix Refinement Finds Every Distinguishing Prefix Within m′ Refinement StepsResearch Paper
Sorting a collection of strings in lexicographic order is a basic subroutine in compilers, string indexing, suffix sorting and the construction of tries. The classical method, due to Aho, Hopcroft and Ullman (The Design and Analysis of Computer Algorithms, 1974), is a multipass radix sort that processes the strings from the last position to the first and…
Dual Stochastic Dominance and Related Mean-Risk Models 1: Second-Degree Stochastic Dominance Is Dominance of Absolute Lorenz CurvesResearch Paper
Comparing uncertain outcomes is the basic problem of decision making under risk. Second-degree stochastic dominance (SSD) is the comparison that every risk-averse decision maker who prefers larger outcomes agrees with: X dominates Y in this sense exactly when EU(X)≥EU(Y) for every nondecreasing concave utility U for which the…
λ1, Isoperimetric Inequalities for Graphs, and Superconcentrators 2: Cayley Graphs of Finite Quotients of a Property (T) Group Are Linear EnlargersResearch Paper
An expander is a sparse graph in which every set of vertices has many neighbours outside itself. Expanders are the building blocks of superconcentrators (sparse directed graphs that route any r inputs to any r outputs along vertex-disjoint paths), of sorting and switching networks, and of many constructions in complexity theory and coding; the survey of…
Robust Control of Markov Decision Processes with Uncertain Transition Matrices 4: The Dual of the Worst-Case Expectation over a Kullback-Leibler BallResearch Paper
A robust Markov decision process replaces the unknown transition probabilities of an MDP by sets of plausible values and optimises against the worst case. Nilim and El Ghaoui (Oper. Res. 53 (2005)) showed that, when the uncertainty is rectangular (each row of each transition matrix varies independently in its own set), the robust problem is solved by a…
λ1, Isoperimetric Inequalities for Graphs, and Superconcentrators 1: A Diameter Bound from λ1Research Paper
The eigenvalues of the Laplacian of a graph carry metric information about the graph. The second-smallest one, λ1(G), was named the algebraic connectivity by Fiedler (Fiedler 1973), who showed it is positive exactly for connected graphs. N. Alon and V. D. Milman (J. Combin. Theory Ser. B 38 (1985) 73–88) showed that a large λ1 also forces two…
Robust Control of Markov Decision Processes with Uncertain Transition Matrices 3: Stationary Policies Suffice and the Stationary/Time-Varying Uncertainty Gap Vanishes GeometricallyResearch Paper
A Markov decision process (MDP) is controlled with transition probabilities estimated from data, and optimal policies computed for the estimated model can perform badly when the estimates are off. Robust MDPs replace the single transition model by a set of models and optimize the worst case over that set. Two readings of "the set" are possible. In the statio…
A Linear-Time Algorithm for Finding a Sparse k-Connected Spanning Subgraph of a k-Connected Graph 2: FOREST's Forests E_i Preserve Local Node-Connectivity up to i in a Simple GraphResearch Paper
Given a k-connected graph, many connectivity algorithms run in time that grows with the number of edges ∣E∣. A sparse certificate is a spanning subgraph with only O(k∣V∣) edges that is still k-connected; computing one first and running the expensive algorithm on it replaces ∣E∣ by k∣V∣ in the bound. Finding a k-connected spanning subgraph with the minimum…
A Linear-Time Algorithm for Finding a Sparse k-Connected Spanning Subgraph of a k-Connected Graph 1: The FOREST Decomposition Preserves Local Edge-ConnectivityResearch Paper
Many graph algorithms for connectivity questions run in time proportional to the number of edges. When the question is only whether a graph is k-edge-connected, or what its local edge-connectivities are up to a threshold k, most edges are irrelevant: a spanning subgraph with O(k∣V∣) edges already carries the answer. Such a subgraph is called a sparse…
Disjunctive Programming VI: Extended Formulations for Perfectly Matchable Subgraph PolytopesTextbook
Many polytopes that arise from combinatorial optimization problems have no small facet
description in their natural variable space, yet become describable by a compact linear system
once lifted to a higher-dimensional space of auxiliary variables and projected back down —
Chapter 2's own extended formulation of the convex hull of a disjunctive set is one…
The Relaxation Method for Linear Inequalities II: For a Lower-Dimensional Solution Polytope Infinite Reflexions Settle on a Sphere with Axis L_rResearch Paper
Adversarially Robust Generalization Requires More Data 4: Robust Learning from One Thresholded Sample in the Bernoulli ModelResearch Paper
Classifiers trained to high standard accuracy can be fooled by small, deliberately chosen perturbations of their inputs, so-called adversarial examples (Szegedy et al., 2014; Goodfellow et al., 2015). Training methods that aim at robustness against perturbations bounded in the ℓ∞ norm reach high robust accuracy on the training set while robust test…
The Relaxation Method for Linear Inequalities I: For a Full-Dimensional Solution Polytope the Relaxation Converges and the Reflexion Method TerminatesResearch Paper
Finding a point that satisfies a finite system of linear inequalities is the feasibility problem underlying linear programming, and it is also the basic step of many methods in signal and image reconstruction, where the system is too large to be solved by elimination. The relaxation method attacks it one inequality at a time: from the current point, move…
Adversarially Robust Generalization Requires More Data 2: A Robust-Error Lower Bound for Linear Classifiers in the Bernoulli ModelResearch Paper
Classifiers trained by standard methods reach high accuracy on image benchmarks and yet change their prediction under perturbations of each pixel that are invisible to a human. Training against such perturbations (adversarial training) improves robustness, but on CIFAR10 and SVHN the robust test accuracy stays far below the robust training accuracy: robust…
On Controllability of Delayed Boolean Control Networks: Trajectory Controllability Avoiding Forbidden Trajectories Iff the Reduced Transition-Count Matrix Is IrreducibleResearch Paper
Boolean networks model gene regulatory networks by giving each gene an on/off value and updating all values synchronously by logical rules (Kauffman, 1969). Adding external Boolean inputs gives Boolean control networks (BCNs), in which a designer (a drug, an intervention) chooses the inputs over time. The basic control-theoretic question is controllability:…
Cones of Matrices and Set-Functions and 0–1 Optimization III: The Defect of a Stable Set Inequality Bounds Its N-IndexResearch Paper
Many 0–1 optimization problems can be written as linear programs over the convex hull of the 0–1 points of a polytope, but that hull usually has no manageable description by inequalities. Lift-and-project methods approximate it by a sequence of convex sets. Each set comes from a linear or semidefinite system in more variables, followed by a projection.…
Cones of Matrices and Set-Functions and 0–1 Optimization I: n Rounds of the Lovász–Schrijver N Operator Give the 0–1 HullResearch Paper
A 0–1 integer program asks for the best 0–1 vector satisfying a system of linear inequalities. Its linear relaxation is easy to optimize over, but the relaxation is usually much larger than the convex hull of the 0–1 solutions. Lift-and-project methods close this gap systematically: they lift the relaxation to a higher-dimensional space, add constraints…