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.
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…
The Distributionally Robust Chance-Constrained Vehicle Routing Problem III: Worst-Case Value-at-Risk Is Additive over Marginalized Moment Ambiguity SetsResearch Paper
The capacitated vehicle routing problem (CVRP) assigns customers to a fleet of m identical vehicles of capacity Q and orders each vehicle's visits so as to minimize transportation cost, subject to each vehicle's total load not exceeding Q. In practice the customers' demands are not known when the routes are planned. Two classical responses are the robust CVR…
Discrete Convex Analysis XXXI: The Potential Criterion for Network FlowsTextbook
Chapter 9 is where discrete convex analysis meets classical network flow theory: the minimum
cost flow problem's three hallmark properties — an optimality criterion by potentials, an
optimality criterion by negative cycles, and integrality of optimal solutions — are shown to
survive, in a precise and increasingly general form, first for arbitrary polyhedral…
The Distributionally Robust Chance-Constrained Vehicle Routing Problem II: Moment Ambiguity Sets Give Subadditive Demand EstimatorsResearch Paper
The capacitated vehicle routing problem (CVRP) asks for a set of minimum-cost routes by which a fleet of identical vehicles of capacity Q, based at a depot, serves every customer exactly once without any vehicle carrying more than its capacity. In practice customer demands are not known when routes are planned. Ghosal and Wiesemann (Oper. Res. 68(3), 2020)…
Tasty Bits of Several Complex Variables II: The Ball and the Polydisc Are Not BiholomorphicTextbook
In one complex variable the Riemann mapping theorem classifies a whole class of domains by topology alone: every nonempty simply connected proper subdomain of C is biholomorphic to the unit disc. Nothing of the kind holds in several variables. The two most obvious generalizations of the disc to Cn, the unit ball and the unit polydisc, are…
Discrete Convex Analysis XI: Max-Flow Min-Cut for Submodular FlowsTextbook
Chapters 6 through 8 built M-convex and L-convex functions and their conjugacy theory as
abstract combinatorial objects on the integer lattice. Chapter 9 grounds that theory in a
setting every reader already knows: network flows. The chapter's throughline is that the
classical minimum cost flow problem — flows bounded by simple arc capacities, with a single…
Discrete Convex Analysis XXX: Lagrangian Duality for M-Convex ProgramsTextbook
Missions 29-ch08b-conjugacyduality and 30-ch08c-conjugacyduality built the M2-/L2-convex
function classes and proved their conjugacy correspondence is nearly complete. This mission
finishes that correspondence (Theorems 8.48-8.49) and then turns to chapter 8's capstone
application: a Lagrangian duality theory for integer programs, built entirely from the…
Applied Combinatorics X: The Lovász Local Lemma and the Gale–Ryser TheoremTextbook
Chapter 16 of Keller and Trotter's Applied Combinatorics (2017 Edition, CC BY-SA 4.0) is a survey of seven topics. Two of them are self-contained results with complete proofs on the page, and this mission formalizes both.
Many counting questions ask for the number of objects up to symmetry: necklaces of coloured beads that may be rotated and flipped, musical scales up to transposition, chemical isomers up to the symmetries of a molecule, graphs on n vertices up to relabelling. Counting all configurations and dividing by the number of symmetries fails, because some…
Applied Combinatorics VIII: The Max Flow–Min Cut TheoremTextbook
Moving as much as possible of something — freight, water, data — from an origin to a destination through connections of limited capacity is one of the basic problems of operations research. Its mathematical form, the maximum flow problem, was posed in the 1950s in work on rail networks and solved independently by Ford and Fulkerson (Maximal flow through a…
Applied Combinatorics VI: Ramsey's Theorem and Erdős's Lower BoundTextbook
Ramsey theory studies the principle that complete disorder is impossible: every sufficiently large structure contains a large, perfectly uniform substructure. Its most familiar instance concerns graphs. In any graph on six vertices there are three vertices that are pairwise adjacent or three that are pairwise non-adjacent, and the same phenomenon persists…
Applied Combinatorics V: Linear Recurrence Equations and the Advancement OperatorTextbook
Linear recurrences with constant coefficients are among the first tools of enumerative combinatorics and the analysis of algorithms: the Fibonacci numbers, the number of binary strings avoiding a pattern, the running time of a divide-and-conquer loop and the number of tilings of a strip all satisfy relations of the form …