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.
On Certain Polytopes Associated with Graphs V: Zero-One Optima of the Odd-Cycle Relaxation on Series-Parallel GraphsResearch Paper
The stable set problem asks for a largest set of pairwise non-adjacent vertices in a graph; its size is the stability numberα(G). It is NP-hard in general, and a standard way to attack it in integer programming is to write down linear inequalities valid for all stable sets and solve the resulting linear program. The weakest such relaxation uses only…
Approximation Techniques for Average Completion Time Scheduling I: Best-α on One Machine with Release DatesResearch Paper
Minimizing the average completion time of jobs that arrive over time is one of the basic objectives of machine scheduling: it measures how long, on average, a job waits in the system. On a single machine with release dates and no preemption (written 1∣rj∣∑Cj), the problem is strongly NP-hard, so research has focused on approximation algorithms whose…
The Power of Convex Relaxation: Near-Optimal Matrix Completion III: No Method Recovers Incoherent Rank-r Matrices below the Sampling Rate (I.20)Research Paper
Matrix completion asks to recover a matrix from a small random subset of its entries. It models collaborative filtering (a ratings table with most entries missing), sensor-network localisation from partial distance data, and system identification. With no structure the task is hopeless, so one assumes the matrix has low rankr and that its information is…
Generalization Bounds in the Predict-then-Optimize Framework II: Margin-Based Generalization Bound for the SPO Loss under the Strength PropertyResearch Paper
In the predict-then-optimize paradigm a model first predicts the cost vector of a linear optimization problem from contextual features, and the prediction is then fed to an optimization solver that returns a decision. Examples include routing with predicted travel times and portfolio choice with predicted returns. The quality of a prediction is judged by…
Local Search Heuristics for k-Median and Facility Location Problems III: Add-Drop-Swap Local Search for Uncapacitated Facility Location Has Locality Gap 3Research Paper
The uncapacitated facility location (UFL) problem is one of the basic models of location theory and operations research: a firm chooses which warehouses, plants or servers to open, paying a fixed cost for each open site and a service cost for every client according to its distance to the nearest open site. It is also a standard test case for approximation…
Multi-armed Bandit Allocation Indices I: The Gittins Index, Optimal Stopping and MonotonicityTextbook
A decision-maker has n projects, each a Markov reward process, and at every decision time may advance exactly one of them; the others stay frozen. Which project to advance so as to maximize the expected total discounted reward? Posed as a dynamic program the problem has a state space that is the product of the n state spaces, and the size of that product…
The Theory and Practice of Revenue Management II: OverbookingTextbook
Every airline, hotel and car-rental firm sells more reservations than it has capacity, because
some customers cancel or do not show. Chapter 4 of Talluri and van Ryzin's The Theory and
Practice of Revenue Management (2004) is the theory of that
decision. Its static models pick one overbooking limit from the show distribution; its dynamic
model, a…
The Theory and Practice of Revenue Management I: Single-Resource Capacity ControlTextbook
An airline sells one flight, a hotel one night, a car-rental firm one day of one car: a fixed
capacity, perishable at a deadline, sold to customers who arrive over time and are willing to
pay different amounts. Chapter 2 of Talluri and van Ryzin's The Theory and Practice of Revenue
Management (2004) is the theory of that single resource. Its
three models…
Fundamentals of Supply Chain Theory VII: Multiechelon Inventory ModelsTextbook
A serial supply chain is the simplest multiechelon system: a retailer orders from a warehouse,
which orders from a plant, which orders from an outside supplier with unlimited stock. Only the
retailer sees customer demand, only the retailer pays a stockout penalty, and every stage pays
to hold inventory. Choosing how much each stage should hold looks like a…
Markov Processes: Characterization and Convergence VII: Strong approximation of independent sumsTextbook
A sum of independent random increments is a basic model for accumulated noise. A continuous Gaussian process offers a different description of that noise, one that can be studied at every nonnegative time. To compare their individual trajectories, both objects must live on the same probability space. The question is whether their paths can remain close over…
Resource Allocation and Cross-Layer Control in Wireless Networks I: The Network Layer Capacity RegionTextbook
Every wireless network control algorithm — routing, scheduling, power control, admission control
— is ultimately judged against one question: which traffic loads can it keep stable? Answering
that question requires a precise, algorithm-independent notion of queueing stability under
random arrivals and a randomly time-varying, possibly non-ergodic-looking…
Markov Processes: Characterization and Convergence 12: Strong approximation of independent sumsTextbook
Independent sums are a basic model for accumulated random fluctuation. A central limit theorem describes their distribution at one large time, and a functional limit theorem describes weak convergence of a rescaled path. Strong approximation asks for substantially more: construct the sums and a Brownian motion on one probability space so that their paths…
The Design of Competitive Online Algorithms via a Primal-Dual Approach VII: Online Group Steiner TreesTextbook
The group Steiner tree problem generalizes the ordinary Steiner tree problem: given a rooted
tree and several groups of vertices, find a minimum-cost subtree that connects at least one
vertex of each group to the root. It is a canonical instance of the generalized-connectivity
family this survey studies in Chapter 11 — a family that also contains the online…
The Design of Competitive Online Algorithms via a Primal-Dual Approach IV: Generalized CachingTextbook
Caching is a two-level memory-management problem — the fast level (cache) can hold only k
items, and the algorithm must decide, online, which item to evict whenever the current request
misses — that is normally analyzed through the competitive ratio of ad hoc marking or LRU-style
rules. Buchbinder and Naor's survey [1] instead recasts weighted caching…
The Design of Competitive Online Algorithms via a Primal-Dual Approach II: The Online Set-Cover ProblemTextbook
Section 4 of this survey derives a simple randomized O(logmlogn)-competitive algorithm for
the online set-cover problem, by rounding the fractional solution the online packing-covering
framework produces. An intriguing question the survey poses next: can the same guarantee be
achieved deterministically? The standard tool for removing randomness, the…
Wasserstein Distributionally Robust Optimization IV: Regularization by Robustification in Classification and RegressionTextbook
Regularization — adding a penalty on model complexity to an empirical risk minimization
objective — is one of the oldest and most reliably effective tools in statistical learning: ridge
regression, LASSO, and margin-based support vector machines all fit this template. For decades the
regularization weight and penalty function were chosen heuristically or by…
Stochastic Orders I: The Usual Stochastic Order and Its Coupling CharacterizationTextbook
Operations research and applied probability are full of questions of the shape "is X riskier,
larger, or later than Y?" when X and Y are random: two queueing disciplines' waiting times, two
inventory policies' shortfall, two insurance portfolios' claim size. Comparing their means answers
a weaker question than the modeler usually wants, since two…
Foundations of Machine Learning XI: Maximum Entropy Models and DualityTextbook
Maximum entropy (Maxent) models are a widely used family of density-estimation algorithms:
given a sample and a set of features, they select the distribution that matches the empirical
feature averages while being otherwise as "agnostic" (close to a prior, usually uniform) as
possible — a principle that, notably, never requires specifying a parametric…
Foundations of Machine Learning VIII: Multi-Class Classification and the Margin BoundTextbook
Every generalization bound in chapters 2-5 is for binary classification. Most real-world
classification problems have more than two classes, and the number of classes can itself be
in the hundreds or thousands (topic classification, speech recognition). Chapter 9 extends the
margin-based generalization theory of chapter 5 (SVMs) to this multi-class,…
High-Dimensional Statistics XI: The Moore-Aronszajn TheoremTextbook
Many statistical problems — nonparametric regression, density estimation, dimension
reduction, testing — are naturally posed as optimization over a space of functions rather
than a finite-dimensional parameter vector. Hilbert spaces provide the right generality: they
carry an inner product and a norm, so notions of projection, orthogonality and…
Stochastic Orders IX: The PQD and Supermodular OrdersTextbook
The first eight chapters of Shaked and Shanthikumar's Stochastic Orders (Springer, 2007) compare
single random variables — location, variability, convexity. Chapter IX turns to a different
question: given two coordinates of a random vector, how strongly do they tend to move together?
"Large values of X1 go with large values of X2" is a qualitative…
High-Dimensional Statistics VI: The Lasso's l2-Error Bound under Restricted EigenvalueTextbook
Modern regression problems routinely have far more candidate predictors than
observations: genomics with tens of thousands of genes and a few hundred patients,
signal recovery from far fewer measurements than the signal's ambient dimension, image
reconstruction from an undersampled set of linear projections. In every such setting
the classical least-squares…
Support Vector Machines IV: The Representer Theorem for Empirical SVM SolutionsTextbook
Support vector machines (SVMs) are trained by solving a regularized empirical risk minimization
problem over a reproducing kernel Hilbert space (RKHS) — a space that is typically
infinite-dimensional. On its face, this looks computationally hopeless: how can a computer
search an infinite-dimensional space for a minimizer? The representer theorem is the…
Stochastic Orders V: The Laplace Transform OrderTextbook
Many of the orders in Shaked and Shanthikumar's Stochastic Orders (Springer, 2007) are built by
fixing a class of test functions φ and declaring X≤Y whenever E[φ(X)]≤E[φ(Y)] for every φ in that class: all increasing functions give the usual
stochastic order, all convex functions give the convex order. This mission formalizes…
High-Dimensional Probability VIII: Dudley's Integral InequalityTextbook
Many questions in high-dimensional probability reduce to bounding the expected supremum of a
random process (Xt)t∈T — the maximum, over an entire indexed family of random variables,
of how large any one of them can get. When T is finite this is routine (a union bound over
∣T∣ terms suffices), but the interesting cases have T infinite, even…