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.
Methods of Conjugate Gradients for Solving Linear Systems I: Finite Termination of the Conjugate Gradient MethodResearch Paper
Solving a linear system Ax=k with a large symmetric positive definite matrix A is a basic task of scientific computing: it arises from discretized elliptic equations, least-squares problems and the Newton steps of optimization methods. In 1952 Magnus Hestenes and Eduard Stiefel published the conjugate gradient method (cg-method) (J. Res. Natl. Bur. Stand.…
Logarithmic Regret Algorithms for Online Convex Optimization 4: Logarithmic Regret of Exponentially Weighted Online OptimizationResearch Paper
In online convex optimization a player repeatedly chooses a point xt from a convex set P⊆Rn, after which an adversary reveals a convex cost function ft and the player pays ft(xt). The player's regret after T rounds is its total cost minus the cost of the best fixed point in hindsight. The model covers online portfolio selection,…
Logarithmic Regret Algorithms for Online Convex Optimization 3: Logarithmic Regret of Follow the Approximate LeaderResearch Paper
Online convex optimization models repeated decision making against an adversary: in each round a player chooses a point of a convex set, and only then learns the convex cost of that round. It covers online portfolio selection, online regression and routing, and it is the standard lens for analysing learning algorithms that must commit before seeing data.…
The Optimal Sample Complexity of PAC Learning: The Optimal Realizable Sample Complexity BoundResearch Paper
The sample complexity of a learning problem is the number of labelled examples needed to learn to a prescribed accuracy with a prescribed confidence. In Valiant's probably approximately correct (PAC) model it is the basic quantity of statistical learning theory: it says how much data is necessary and sufficient, as a function of the complexity of the…
Optimizing Strategic Safety Stock Placement in Supply Chains: Binding Base Stocks Are Optimal in a Serial System without Guaranteed Internal ServiceResearch Paper
Where to hold safety stock in a multi-stage supply chain is a basic question of inventory planning. Graves and Willems (MSOM 2(1), 2000) optimize safety-stock placement under the guaranteed-service assumption: each stage quotes a service time to its customers and always meets it. That assumption makes the placement problem tractable, and it is the basis of…
Maximizing Non-Monotone Submodular Functions I: A Uniformly Random Set Achieves 1/4 of the Optimum, and 1/2 for Symmetric FunctionsResearch Paper
Many combinatorial optimization problems ask for a subset of a finite ground set that maximizes a set function with diminishing returns: Max Cut and Max Directed Cut in graphs, facility location, maximum entropy sampling, and welfare problems in combinatorial auctions all fit this pattern. The common abstraction is the maximization of a submodular function,…
Scenario Reduction in Stochastic Programming: The Optimal Redistribution Rule and the Explicit Kantorovich Distance of a Reduced MeasureResearch Paper
Stochastic programs are solved in practice on a finite set of scenarios: a discrete probability distribution P=∑i=1Npiδωi that approximates the true distribution of the uncertain data. The size of the resulting deterministic problem grows with N, and for multistage models it grows very fast, so N is often reduced before solving. The…
A Social Equilibrium Existence Theorem: Equilibrium Points Exist When Actions Are Contractible Polyhedra and Constrained Best Responses Are ContractibleResearch Paper
Nash's equilibrium existence theorem assumes that each player's set of available strategies is fixed. Many social and economic systems do not work that way: a consumer's budget set depends on prices, which are the choices of another agent, and a firm's feasible production may depend on what other firms do. Gerard Debreu's A Social Equilibrium Existence…
Approximation Techniques for Average Completion Time Scheduling IV: List Scheduling from an Optimal One-Machine Schedule Is a 2-Approximation for In-TreesResearch Paper
Minimizing the sum of weighted completion times of jobs on identical parallel machines is one of the basic objectives of machine scheduling: it measures the average time a job spends in the system, weighted by its importance. When the jobs are subject to precedence constraints (a job may start only after certain other jobs have finished), the problem is…
Approximation Techniques for Average Completion Time Scheduling III: From One Machine to Many with Delay ListResearch Paper
Minimizing the sum of weighted completion times∑jwjCj is one of the standard objectives of machine scheduling: it measures the average time a job spends in the system, weighted by its importance. With release dates or precedence constraints the problem is NP-hard already on one machine, and on m identical parallel machines it is harder still, so the…
Approximation Techniques for Average Completion Time Scheduling II: A 2.83-Approximation for Parallel Machines with Release DatesResearch Paper
Minimizing the average completion time of jobs that arrive over time is a basic objective in machine scheduling. It measures how long a job spends in the system on average. With several identical machines, release dates and no preemption (written P∣rj∣∑Cj), the problem is strongly NP-hard already on one machine. Research has therefore looked for…
The Allocation of Inventory Risk in a Supply Chain: Push, Pull, and Advance-Purchase Discount Contracts 3: Advance-Purchase Discounts Pareto-Improve Pull Contracts under At-Once Shipping CostsResearch Paper
A supplier and a retailer who trade a seasonal product must decide who carries the inventory risk: the stock left unsold, or the demand left unserved, when the season ends. With a push contract the retailer orders everything before the season and bears the risk; with a pull contract he orders during the season from the supplier's stock at a single wholesale…
The Allocation of Inventory Risk in a Supply Chain: Push, Pull, and Advance-Purchase Discount Contracts 2: Advance-Purchase Discounts Coordinate the Supply ChainResearch Paper
A supplier who must produce before a selling season, and a retailer who sells into uncertain demand, have to decide who holds the inventory that may go unsold. Cachon (Management Science 50(2), 2004) studies this allocation of inventory risk using nothing but wholesale prices. With a push contract the retailer orders everything before production and bears…
The Allocation of Inventory Risk in a Supply Chain: Push, Pull, and Advance-Purchase Discount Contracts 1: The Pareto Set of Push and Pull ContractsResearch Paper
A supplier and a retailer trade a product with a single selling season and uncertain demand. Someone has to decide, before demand is known, how many units exist, and someone has to be left holding the units that do not sell. With a push contract the retailer orders (prebooks) before the season and bears all of this risk; with a pull contract the supplier…
Generalization Bounds in the Predict-then-Optimize Framework III: Strongly Convex Sets Satisfy the Strength PropertyResearch Paper
In the predict-then-optimize framework, a machine-learning model predicts the cost vector c^ of a linear optimization problem minw∈Sc^⊤w, and a decision is made by solving that problem with the prediction. Elmachtoub and Grigas (Smart "Predict, then Optimize", Management Science 2022) proposed judging predictions by the SPO loss, the…
Local Search Heuristics for k-Median and Facility Location Problems IV: Local Search with Multi-Copy Moves for Capacitated Facility Location Has Locality Gap 4Research Paper
Facility location asks where to open service points (warehouses, plants, servers) and how to connect customers to them so that the total opening cost plus the total connection cost is minimum. In the capacitated version each facility can serve only a limited number of customers, which is the situation in most applications: a warehouse has a floor area, a…
Local Search Heuristics for k-Median and Facility Location Problems I: Single-Swap Local Search for k-Median Has Locality Gap 5Research Paper
The k-median problem asks where to open k facilities so that the total distance from a set of clients to their nearest open facility is as small as possible. It is a basic model of facility location in operations research (placing depots, warehouses or servers) and of clustering with representative centres, and it is NP-hard, so the question of interest is…
Coherent Multiperiod Risk Adjusted Values and Bellman's Principle: Stability of the Test Probabilities Is Equivalent to Bellman's PrincipleResearch Paper
A coherent risk measure assigns to a future financial position the smallest amount of capital that makes it acceptable to a supervisor. Artzner, Delbaen, Eber and Heath characterised the one-period version: every coherent risk measure has the form π(X)=infQ∈PEQ[X] for a set P of test probabilities (ADEH…
Multi-armed Bandit Allocation Indices VI: Bandit Sampling Processes, Favourable Priors and Invariance of the IndexTextbook
The bandit processes that motivated the index theorem are sampling processes: an arm is a population from which one draws i.i.d. observations whose distribution has an unknown parameter, and each draw both earns something and teaches something. Chapter 7 of Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/97804709800…
Multi-armed Bandit Allocation Indices V: Restless Bandits, Indexability and Whittle Indices for Monotone ModelsTextbook
Every proof of the index theorem in Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/9780470980033), uses the fact that a bandit not being processed is frozen. Chapter 6 drops that: Whittle's restless bandits evolve under the passive action too, by a different law, and m of n must be active at every time. The…
Multi-armed Bandit Allocation Indices IV: The Achievable Region, Generalized Conservation Laws and the Adaptive Greedy AlgorithmTextbook
Chapter 5 of Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/9780470980033), presents the achievable region methodology of Tsoucas, Bertsimas and Niño-Mora, Glazebrook and Garbe, and Dacre, Glazebrook and Niño-Mora: instead of arguing about policies, one argues about the set of performance vectors they can produce.…
Introduction to Multi-Armed Bandits XI: Bandits and Agents, Incentivized Exploration via Hidden ExplorationTextbook
A recommendation system learns from the users it serves: the diner who tries a restaurant produces the review the next diner reads. Each user would rather exploit what is already known than explore for the benefit of those who come later, so a population of self-interested agents under-explores, and an alternative that looks bad on sparse early evidence may…
The Theory and Practice of Revenue Management IV: AuctionsTextbook
Airlines selling last seats, Priceline's name-your-own-price, procurement of supply contracts:
Chapter 6 of Talluri and van Ryzin's The Theory and Practice of Revenue Management
(2004) treats auctions as pricing mechanisms and asks what
revenue they earn and how to design them. Its centre is Myerson's
(1981) theory for independent private values: whatever…
Inventory Control VIII: The Clark-Scarf Decomposition for a Serial SystemTextbook
Chapter 10 of Axsäter's Inventory Control turns to reorder points and safety stocks in
multi-echelon systems, where the installations cannot be treated separately: a large stock
downstream lets an upstream site run lean, and a long upstream lead-time argues for stock at
the top. The best-known exact technique for serial systems is the decomposition of Clark…