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.
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 …
Applied Combinatorics IV: Newton's Binomial Theorem and the Central Binomial ConvolutionTextbook
Generating functions are the standard device of enumerative combinatorics for turning a counting sequence into a single algebraic or analytic object: a sequence {an:n≥0} is recorded as the power series ∑n≥0anxn, and operations on series (products, powers, derivatives) become operations on the counts. Chapter 8 of Keller and Trotter's App…
Discrete Convex Analysis IX: The Discrete Conjugacy TheoremTextbook
The Legendre-Fenchel transform is the single most structurally important operation in convex
analysis: for a proper closed convex function f, its conjugate f∙(p)=supx{⟨p,x⟩−f(x)} is again proper closed convex, and the transform is an
involution — f∙∙=f. This one fact underlies duality theory across
optimization:…
Partially ordered sets model precedence: tasks that must wait for other tasks, versions that
supersede others, files nested in directories, alternatives ranked by several criteria at once.
Two questions about such a structure recur in scheduling and in the design of algorithms. How
many sequential "threads" are needed so that every item lies on a thread in…
Notes on Partial Differential Equations X: Galerkin Existence of Weak Solutions of Parabolic PDEsTextbook
Linear second-order parabolic equations such as ut+Lu=f model diffusion with advection, growth or decay, and external sources. The heat equation is the prototype. For coefficients that are only bounded and measurable, classical solutions need not exist, and the natural well-posedness theory is the L2 energy theory of weak solutions. In that theory the…
Discrete Convex Analysis VIII: Quasi L-Convex Functions and the Quasi-Proximity TheoremTextbook
Milgrom and Shannon's theory of quasi-supermodularity, developed for monotone comparative
statics in economics, showed that many of the consequences of lattice submodularity survive
under a much weaker, purely ordinal relaxation of the defining inequality. Chapter 7's final
section imports this idea into discrete convex analysis: does L-convexity's…
Notes on Partial Differential Equations VIII: Strongly Continuous Semigroups and the Lumer–Phillips TheoremTextbook
Many linear partial differential equations of evolution type — the heat equation, the Schrödinger equation, linear wave and Klein–Gordon equations, linearized reaction–diffusion and Kuramoto–Sivashinsky equations — can be written as an ordinary differential equation
Markov Decision Processes XIX: Theory of Optimal Stopping ProblemsTextbook
A gambler watching a sequence unfold has to decide, at each moment and knowing only the past,
whether to take what is on the table or wait for something better. That is the whole of optimal
stopping, and it is one of the few problems in stochastic control with a clean and completely
general answer: the value of the problem is the smallest superharmonic…
Notes on Partial Differential Equations II: The Newtonian Potential and Hölder Estimates for Poisson's EquationTextbook
Poisson's equation−Δu=f is the model elliptic partial differential equation. It describes the electrostatic potential of a charge density, the gravitational potential of a mass density, and the steady temperature of a body with internal heat sources. Its solution on the whole space by convolution with a point-source potential, and the fact that…
Calibrated Learning and Correlated Equilibrium II: For Almost Every Game, Limits of Calibrated Learning Are Exactly the Correlated EquilibriaResearch Paper
A correlated equilibrium (Aumann, 1974) is a joint distribution over the players' strategy profiles from which no player gains by deviating from a recommended strategy. A central question of learning in games is which equilibria repeated play of simple, myopic rules can reach. Foster and Vohra (1997) answered it for calibrated forecasting: if each player…
Discrete Convex Analysis XXI: The Exchange Axiom as Local OptimalityTextbook
Convexity on the integer lattice cannot be defined by the classical secant-line inequality alone:
a function can be midpoint-convex along every line and still admit no useful global optimality
theory, because integer points off a chosen line are invisible to it. M-convex functions,
introduced by Murota, resolve this by replacing the secant condition with an …