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.
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…
Extremal Problems in Discrete Geometry: The Szemerédi–Trotter Incidence BoundResearch Paper
How many times can n points and t lines in the plane meet? The question is the prototype of incidence geometry, and the answer controls a long list of problems in discrete and computational geometry: the number of lines rich in points, the number of distinct distances or unit distances among n points, the complexity of arrangements, and sum–product…
Ordinary Differential Equations and Dynamical Systems XI: The Smale HorseshoeTextbook
The Smale horseshoe is the standard example of a smooth invertible map of the plane with chaotic dynamics. Smale introduced it in the 1960s as the mechanism behind the complicated orbits near a transverse homoclinic point, and it became the basic model of hyperbolic invariant sets (Smale 1967). Its importance for differential equations is the Smale–Birkhoff…
Ordinary Differential Equations and Dynamical Systems X: Periodic Orbits and the Poincaré MapTextbook
Periodic solutions are the simplest non-stationary long-time behaviour of an autonomous system x˙=f(x): limit cycles in oscillators and population models, closed orbits of conservative systems. The first question about a periodic orbit is whether it is stable. Poincaré introduced the first-return map on a transversal section, which turns this question…
Algorithmic Mechanism Design VI: With Verification, the Compensation-and-Bonus Mechanism Is a Strongly Truthful Optimal ImplementationResearch Paper
Scheduling tasks on machines owned by self-interested parties is the running example of Nisan and Ronen's Algorithmic Mechanism Design (Games and Economic Behavior 35, 2001), the paper that introduced the study of mechanisms whose allocation rule is an algorithm with a computational objective. Each machine (agent) privately knows how long it needs for each…
Algorithmic Mechanism Design V: The Randomly Biased Min Work Mechanism Is a Strongly Truthful 7/4-Approximation for Two AgentsResearch Paper
Algorithmic mechanism design, introduced by Nisan and Ronen (Games Econ. Behav. 35, 2001), studies optimization problems whose input is held by self-interested agents. Each agent reports its private data to a protocol, and the protocol must choose an output and payments so that reporting the truth is in every agent's interest while the chosen output is…
Algorithmic Mechanism Design IV: No Local Truthful Mechanism Achieves a c-Approximation for Task Scheduling for Any c < nResearch Paper
Nisan and Ronen's Algorithmic Mechanism Design (Games and Economic Behavior 35, 2001) asks how well a computational task can be carried out when its inputs are held by self-interested agents who may lie about them. Their test case is scheduling on unrelated machines: tasks must be assigned to agents (machines), each agent privately knows how long it needs…
Ordinary Differential Equations and Dynamical Systems IX: Interval Maps, Symbolic Dynamics and the Tent-Map RepellorTextbook
One-dimensional maps are the smallest systems in which deterministic dynamics becomes unpredictable. Chapter 11 of Gerald Teschl's graduate text Ordinary Differential Equations and Dynamical Systems (author's version; AMS Graduate Studies in Mathematics 140, 2012, doi:10.1090/gsm/140) uses them to make the word "chaos" precise. The chapter proves that a…
Algorithmic Mechanism Design II: A Lower Bound for Truthful Task SchedulingResearch Paper
Algorithms deployed on the Internet often take their inputs from parties who own them and who may lie when lying pays. Nisan and Ronen's Algorithmic Mechanism Design (Games and Economic Behavior 35, 2001) proposed studying optimization problems in this setting: the algorithm designer may hand out payments, and must guarantee that the intended output is…
Ordinary Differential Equations and Dynamical Systems VI: The Poincaré–Bendixson TheoremTextbook
Long-time behaviour is the central question about an autonomous differential equation x˙=f(x): where does a trajectory go as t→±∞? In the plane this question has an almost complete answer. The theory begun by Poincaré (Mémoire sur les courbes définies par une équation différentielle, 1881–1886) and completed by Bendixson (Sur les courbes…
Ordinary Differential Equations and Dynamical Systems V: Limit Sets and the Krasovskii–LaSalle PrincipleTextbook
Most differential equations that model physical, biological or engineered systems cannot be solved in closed form, yet the question asked about them is usually qualitative: does the system settle down to an equilibrium, and does it stay near the equilibrium when perturbed? Liapunov's direct method answers that question without solving the equation, by…
Ordinary Differential Equations and Dynamical Systems I: Existence, Uniqueness and Peano's TheoremTextbook
Almost every quantitative statement about an ordinary differential equation, from the stability of an equilibrium to the existence of a periodic orbit, presupposes that the equation has a solution through each initial point and, usually, that this solution is unique and depends continuously on the data. Chapter 2 of Gerald Teschl's graduate textbook Ordinary…
Single Machine Scheduling with Release Dates III: The Random Per-Job α-Schedule with a Truncated Exponential DensityResearch Paper
Scheduling jobs with release dates on one machine to minimize the total weighted completion time, written 1∣rj∣∑wjCj, is strongly NP-hard even with unit weights (Lenstra, Rinnooy Kan & Brucker, 1977). It is a basic model of scheduling theory and a standard testbed for approximation algorithms built on linear programming relaxations. Several LP…
Single Machine Scheduling with Release Dates II: The Random α-Schedule with a Truncated Exponential DensityResearch Paper
Minimizing the total weighted completion time∑jwjCj of jobs with release dates on a single machine, written 1∣rj∣∑wjCj in scheduling notation, is strongly NP-hard. It is one of the basic models of machine scheduling, and it has served as a test case for a general technique in approximation algorithms: solve a linear programming…
On the Global Convergence of Stochastic Fictitious Play II: Almost Sure Convergence in Zero-Sum Games and Symmetric Games with an Interior ESSResearch Paper
Fictitious play is the oldest model of learning in games: players repeatedly play a fixed normal form game, and each round every player best-responds to the empirical frequencies of the opponents' past play. Brown (1951) proposed it as an algorithm for computing the value of a zero-sum game, and Robinson (1951) proved that the empirical frequencies converge…
Tasty Bits of Several Complex Variables VI: The Hartogs PhenomenonTextbook
In one complex variable every open set is the natural domain of some holomorphic function: 1/z on a punctured disc cannot be continued across the puncture. In two or more variables this fails in a striking way. Hartogs observed in 1906 that a function holomorphic on the complement of a compact set inside a domain always extends across the hole (Hartogs,…
On the Global Convergence of Stochastic Fictitious Play I: Every Additive Random Utility Choice Function Has an Admissible Deterministic Perturbation RepresentationResearch Paper
Models of learning in games, and discrete choice models in econometrics, describe an agent who does not always pick the best alternative. Two descriptions of such an agent are standard. In the additive random utility model (McFadden 1981; Anderson, de Palma and Thisse 1992) the agent maximizes payoffs perturbed by random shocks. In the deterministic…
Discrete Convex Analysis XIV: The König-Egerváry Theorem for Mixed MatricesTextbook
Every physical or engineering model built from linear relations mixes two kinds of numbers.
Some coefficients are exact — the ±1 entries recording Kirchhoff's current and voltage
laws in an electrical network, or the incidence structure of a mechanical linkage — because they
come from a topological or combinatorial fact, not a measurement. Others are…
Discrete Convex Analysis XXXV: Gross Substitutes and Equilibrium PricesTextbook
This mission continues chapter 11's account of the M♮-concave/M♮-convex exchange-economy model
begun in mission 14-economic-equilibrium, placing seven of that chunk's own results that were
previously left out-of-cone: the two gross-substitutes-style characterizations of M♮-concavity
(§11.3), the transfer theorem that lifts an equilibrium of the continuous…
The Distributionally Robust Chance-Constrained Vehicle Routing Problem V: Worst-Case Value-at-Risk over Covariance Ambiguity Sets as a Quadratically Constrained ProgramResearch Paper
In the capacitated vehicle routing problem (CVRP) a fleet of m vehicles of capacity Q leaves a depot and serves n customers; every customer is visited once, and the load of each route must not exceed Q. In practice customer demands are uncertain at planning time. The chance-constrained CVRP asks that each route respect the capacity with probability at least …
The Distributionally Robust Chance-Constrained Vehicle Routing Problem IV: Worst-Case Value-at-Risk over First-Order Generic Moment Ambiguity Sets as a Convex ProgramResearch Paper
In the capacitated vehicle routing problem (CVRP) a depot serves customers VC={1,…,n} with m vehicles of capacity Q, and every route must respect the capacity. When customer demands are uncertain, the distributionally robust chance-constrained CVRP of Ghosal and Wiesemann (Oper. Res. 68(3), 2020) requires every route to meet its capacity with…