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.
Minimization Methods for Non-Differentiable Functions II: Convex Functions Are Almost Differentiable and Their Almost-Gradients Are SubgradientsTextbook
Gradient methods assume a continuous gradient; subgradient methods assume convexity. Many objective functions met in practice satisfy neither. Shor's example is economic planning, where components of the objective are piecewise-smooth, not necessarily convex functions of a parameter describing the productivity of a unit, and where minimax formulations…
Stochastic Dynamic Programming and the Control of Queueing Systems XIII: Lyapunov Criteria and z Standard Markov Chains with CostsTextbook
Average cost control of queues rests on a small amount of Markov chain theory: when does a chain with costs have a well defined long-run average cost, and how can that be checked for a concrete model with an unbounded state space? Appendix C of L. I. Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999, doi:10.1002/9780470…
Stochastic Dynamic Programming and the Control of Queueing Systems XII: A Tauberian Theorem Linking Abel and Cesàro Means of Nonnegative SeriesTextbook
In the theory of Markov decision chains two cost criteria dominate: the discounted cost, in which a cost incurred at time n is weighted by αn for a discount factor α∈(0,1), and the average cost, the long-run cost per unit time. A standard route to average cost optimal policies is to solve the discounted problem and let α→1−. That…
Stochastic Dynamic Programming and the Control of Queueing Systems XI: The Generalized Dominated Convergence Theorem for Approximating DistributionsTextbook
Linn Sennott's Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999) studies Markov decision chains with countably many states, finite action sets and unbounded nonnegative costs. Its main computational device, the approximating sequence method (Definition 2.5.1, p. 28), replaces the countable state space S by an increasing…
Stochastic Dynamic Programming and the Control of Queueing Systems X: Average Cost Optimization of Continuous Time Markov Decision ChainsTextbook
Many queueing systems evolve in continuous time: customers arrive according to a Poisson process, services take exponentially distributed times, and a controller may change the service rate, admit or reject customers, or route them whenever the state changes. Minimizing the long-run average cost of such a system is a standard problem in the control of…
Stochastic Dynamic Programming and the Control of Queueing Systems IX: Bounded Mean Residual Lifetimes Imply Finite Moments of All OrdersTextbook
In a discrete-time queue the service of a customer lasts a random number Y of slots. When such a system is modelled as a Markov decision chain (Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems, Wiley, 1999, DOI 10.1002/9780470317037, Chapter 9), the state must record how much service is still owed, and the controller only observes…
Stochastic Dynamic Programming and the Control of Queueing Systems VIII: Computing Average Cost Optimal Policies by Approximating SequencesTextbook
Control problems for queueing systems (admission control, service rate control, routing to parallel servers) are naturally modelled as Markov decision chains whose state is a vector of queue lengths. The state space is therefore denumerably infinite, and the performance measure of interest is usually the long-run average cost per slot. For such models the…
Stochastic Dynamic Programming and the Control of Queueing Systems IV: Average Cost Optimal Stationary Policies Exist for Finite State SpacesTextbook
Controlled queues, inventories and communication links are run for a long time, and the quantity an operator usually cares about is the long-run average cost per period rather than a discounted total. The average cost criterion is harder to work with than the discounted one: its value is a limsup of Cesàro means, it is not given by a contraction, and for…
Stochastic Dynamic Programming and the Control of Queueing Systems II: The Discount Optimality EquationTextbook
Control problems for queueing systems (admission control, routing, service rate selection, inventory replenishment) are naturally modelled as Markov decision chains with a countable state space, such as the number of customers in a buffer, and with costs that grow without bound in the state, such as holding costs proportional to queue length. The expected…
Stochastic Dynamic Programming and the Control of Queueing Systems I: Finite Horizon Optimality and Approximating SequencesTextbook
Controlled queueing systems (admission control, routing, service-rate selection) are naturally modelled as Markov decision chains whose state is a buffer content and therefore ranges over a countably infinite set. Linn Sennott's Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999, DOI 10.1002/9780470317037) develops the dynamic…
Theory of Games and Economic Behavior II: Games with Perfect Information Are Strictly DeterminedTextbook
Chess, checkers, Go and Backgammon share a feature that card games such as Poker lack: whenever a player moves, the player knows everything that has happened so far. von Neumann and Morgenstern call this perfect information and devote §15 of Theory of Games and Economic Behavior (1944; 3rd ed. 1953) to it. Their result is that such a game, viewed as a…
Analysis and Algorithms for Service Parts Supply Chains VIII: Bounds on Optimal Stock AllocationsTextbook
Military and commercial service parts systems keep repairable parts at a central depot warehouse and at a set of operating bases. Chapter 10 of Muckstadt's Analysis and Algorithms for Service Parts Supply Chains (Springer 2005, DOI 10.1007/b138879) turns from the planning models of the earlier chapters to execution. Each period, the stock that is at the…
Extended Smale's 9th Problem I: no algorithm computes K digits of LP minimisersResearch Paper
Linear programming is usually described as "solvable in polynomial time", but that statement is about rational inputs given exactly. In Smale's list of problems for the 21st century (Smale 1998), Problem 9 asks for a polynomial-time algorithm over the reals deciding the feasibility of Ax≥y, and Smale explicitly calls for "models which process…
Monge–Kantorovich Duality (Yao 2023)Research Paper
Optimal transport asks for the cheapest way to move one distribution of mass onto another. Monge posed the problem in 1781 for maps; Kantorovich (1942) relaxed it to transference plans (couplings), turning it into an infinite-dimensional linear program with a dual: maximize the total revenue ∫ψdμ+∫φdν of pickup and delivery prices…
Analysis and Algorithms for Service Parts Supply Chains VI: The Shortfall Distribution of Capacity-Limited SystemsTextbook
Service parts supply chains are often limited by a capacitated resource, such as a production line or a repair shop, instead of by lead times alone. Once capacity binds, the classical tools for setting stock levels (Palm's theorem and the Poisson distribution of units in resupply) no longer apply, and the quantity that determines how much stock is needed is…
Analysis and Algorithms for Service Parts Supply Chains V: Marginal Allocation and Risk PoolingTextbook
Service parts networks (spare parts for aircraft, military systems, industrial equipment) hold stock at several echelons: a depot, intermediate stocking facilities, and bases or warehouses that face demand. Two questions recur in their planning. First, how should a given amount of stock be split among locations whose expected costs are convex in the stock…
Analysis and Algorithms for Service Parts Supply Chains III: Palm's Theorem for (s–1, s) PoliciesTextbook
Service parts (spare engines, avionics modules, repairable components) are usually managed one unit at a time: whenever a customer order removes a unit from stock, a replacement is ordered at once, from a repair shop or an outside supplier. This is the (s–1, s) policy, under which the inventory position (on hand plus on order minus backorders) stays…
Analysis and Algorithms for Service Parts Supply Chains II: The Single-Unit Single-Customer DecompositionTextbook
A base-stock (order-up-to) policy orders, in every period, exactly enough to bring the inventory position (stock on hand plus stock on order minus backorders) up to a target level. It is the policy used in practice for repairable and consumable service parts, and the analysis of every later chapter of Muckstadt's book assumes it. Its optimality is therefore…
Analysis and Algorithms for Service Parts Supply Chains I: Optimality of Order-Up-To Policies by Dynamic ProgrammingTextbook
A stocking point that reviews its inventory once per period and must decide how much to order is the basic unit of every service parts supply chain: each warehouse, each repair depot and each forward location in the networks studied later in Muckstadt's Analysis and Algorithms for Service Parts Supply Chains (Springer 2005, DOI 10.1007/b138879) faces this…
Numerical Techniques for Stochastic Optimization III: Stochastic Quasi-Féjer Sequences and the Stochastic Quasigradient Projection MethodTextbook
Many optimization problems in operations research have an objective that is an expectation, F0(x)=Ef0(x,ω), over a random parameter ω whose distribution is known only through samples or is too complex to integrate. Two-stage stochastic programs, inventory and reliability models, and simulation-based design all have this form. Neither F0 nor…
Introduction to the Scenario Approach V: Support Sets Certify the Violation of Nonconvex Scenario SolutionsTextbook
The scenario approach replaces an optimization problem with uncertain constraints θ∈Θδ, δ∈Δ, by the program that enforces only N constraints Θδ1,…,ΘδN drawn at random from the distribution P of the uncertainty. Its solution θ∗ is then judged by its violation, the probability that a…
Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue: The Competitive Ratio of the Primal-Dual Allocation AlgorithmResearch Paper
Search engines sell advertisement slots next to their results through ad-auctions. Advertisers bid on keywords, and each advertiser also sets a daily budget: the most it is willing to pay in a day. Queries arrive one at a time and each must be assigned to an advertiser at once, with no knowledge of the queries still to come. The seller's revenue from an…
Value of Information in Bayesian Routing Games I: Sign and Monotonicity of the Relative Value of Information Across Size RegimesResearch Paper
Traffic information systems (TIS) such as navigation apps send drivers noisy signals about the state of a road network: incidents, weather, closures. When several such systems coexist, each with its own subscriber base and its own information, a natural question for operators and regulators is whether subscribing to one system rather than another actually…
Computing Optimal (s, S) Inventory Policies III: Selecting an (s, S) Policy That Is Optimal for Every Starting StockResearch Paper
The periodic-review inventory model with a fixed ordering cost is one of the basic models of operations research. When every order incurs a set-up cost K in addition to holding and shortage costs, the optimal replenishment rule over an infinite horizon is, under standard convexity assumptions, a stationary (s,S) policy: whenever the stock falls below the…
Computing Optimal (s, S) Inventory Policies II: Bounds on the Optimal s and S of the n-Period Model from the One-Period CostResearch Paper
The (s,S) policy is the standard ordering rule for a single stocked item with a fixed charge per order: when the stock position falls below a reorder point s, order up to a level S; otherwise order nothing. Scarf (1960) proved that when the expected one-period cost is convex, some (s,S) policy is optimal in every period of a finite-horizon model with…