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 Matrix Analytic Methods in Stochastic Modeling VIII: The Logarithmic Reduction Series for GTextbook
Quasi-birth-and-death processes (QBDs) are Markov chains on pairs (level, phase) in which the level moves by at most one at each step. They model queues in random environments, priority queues, and many other systems treated by matrix-analytic methods (Latouche & Ramaswami 1999). Their stationary distribution, when it exists, is matrix-geometric, and…
Introduction to Matrix Analytic Methods in Stochastic Modeling IX: The Roots of det(x²A₀ + x(A₁ − I) + A₂) and the Eigenvalues of GTextbook
A quasi-birth-and-death process (QBD) is the matrix generalization of a birth-and-death chain: a Markov chain on pairs (level, phase) that moves at most one level per step. QBDs model queues in random environments, multi-server and priority systems, and communication links with correlated traffic, and their analysis rests on two matrices: the first-passage…
Introduction to Matrix Analytic Methods in Stochastic Modeling X: Linear Level Reduction for Finite QBDsTextbook
In a queue with a finite buffer, a multi-server system with a capacity limit, or a communication link with a bounded number of packets in transit, the number of customers is a level that takes only finitely many values, and the rest of the state (service phase, arrival phase, environment) is a phase. The resulting Markov chain is a finite…
Introduction to Matrix Analytic Methods in Stochastic Modeling V: The Matrix-Geometric Stationary Distribution of a QBDTextbook
Quasi-birth-and-death processes (QBDs) are the workhorse models of queueing theory, telecommunications and inventory systems whenever a counting variable (the number of customers, packets or items) moves up or down by one while a second, finite or countable, phase variable records the state of the environment: the phase of a service-time distribution, of an…
Introduction to Matrix Analytic Methods in Stochastic Modeling VI: The Mean-Drift Stability Criterion for QBDsTextbook
Quasi-birth-and-death processes (QBDs) are the standard Markov models of queues with structured arrivals and service: a queue fed by a Markovian arrival process, a server with phase-type service times, a buffer in a telecommunication link with a fluctuating source. Their stationary distribution has the matrix-geometric form πn=π0Rn (Neuts, Matrix-G…
Introduction to Matrix Analytic Methods in Stochastic Modeling IV: The Censored Markov Chain and Its Stationary DistributionTextbook
Matrix analytic methods compute the stationary distribution of structured Markov chains (quasi-birth-and-death processes, M/G/1- and GI/M/1-type chains) by working on one block of states at a time. Every such computation rests on one device: watch the chain only while it is in a subset T of the state space, and describe what happens in between through…
Introduction to Matrix Analytic Methods in Stochastic Modeling III: Recurrence of Birth-and-Death Chains and the Minimal Solution of G = a₂ + a₁G + a₀G²Textbook
Birth-and-death chains are the simplest Markov chains with an unbounded state space. They model a queue that gains or loses one customer at a time, a population that grows or shrinks by one, and a random walk with a reflecting barrier. In matrix analytic methods they serve as the scalar model for quasi-birth-and-death processes (QBDs). A QBD is a chain on…
Introduction to Matrix Analytic Methods in Stochastic Modeling II: The Renewal Function of a PH Renewal ProcessTextbook
Renewal processes model ordered sequences of events on [0,∞): arrivals to a queue, service completions, equipment failures. Their defining feature is that successive intervals between events are independent and identically distributed. Two quantities answer most practical questions about such a process: the renewal functionR(x), the expected number of…
A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach: Binary Search over all-pack Is a (1 + ε)-Approximation for Makespan on Uniform MachinesResearch Paper
Scheduling independent jobs on machines that run at different speeds, so that the last job finishes as early as possible, is one of the basic problems of scheduling theory. In the classification of Graham, Lawler, Lenstra and Rinnooy Kan it is denoted Q∥Cmax, the minimum makespan problem on uniform parallel machines. It is strongly NP-hard, so the…
Introduction to Matrix Analytic Methods in Stochastic Modeling I: PH Distributions and the Absorption CriterionTextbook
Phase-type (PH) distributions are the distributions of absorption times of finite Markov chains. Introduced by Neuts in the 1970s (the book follows his framework, Latouche–Ramaswami, §2.3), they are the standard way to put non-exponential service times, interarrival times and lifetimes into a model while keeping it Markovian: a PH random variable is a walk…
Flows in Networks VII: Maximal Dynamic Flows from Temporally Repeated FlowsTextbook
Many transportation and evacuation questions ask how much can be shipped from a source to a sink within a time horizon, when every arc has both a capacity per period and a traversal time. Ford and Fulkerson posed this maximal dynamic flow problem in 1958 and solved it by a reduction that is now standard in network optimization: instead of solving a linear…
Flows in Networks VIII: Flow Functions Realizable by TreesTextbook
In a communication or transportation network, a planner often needs not one maximal flow value but all of them: the largest amount that can be sent between every pair of locations. For an undirected network with n nodes there are n(n−1)/2 such values. In 1961, R. E. Gomory and T. C. Hu (Multi-terminal network flows, J. SIAM 9 (1961)) answered two questions…
Flows in Networks VI: Zero-One Matrices with Zero TraceTextbook
An m×n matrix of 0's and 1's is the incidence matrix of m sets against n elements, or the adjacency matrix of a bipartite graph, or, when m=n, the adjacency matrix of a directed graph on n nodes. The first question about such matrices is when one exists with prescribed row and column sums. Gale (1957) and Ryser (1957) answered it independently with…
Flows in Networks II: Maximal Flow Value as a Function of Two Arc CapacitiesTextbook
The value of a maximal flow is the basic output of network-flow models of transport, communication and supply systems. A planner who can enlarge the capacity of a link wants to know what the enlargement buys. For a single link the answer is simple. For two links it is a question about interaction: does enlarging one make enlarging the other more valuable…
Flows in Networks I: The Max Flow Min Cut TheoremTextbook
The maximal flow problem asks how much of a commodity can be sent from one node of a network to another when every arc has a capacity. It was posed in the 1950s in the study of rail networks, and its answer, the max flow min cut theorem of L. R. Ford, Jr. and D. R. Fulkerson, became the organizing result of combinatorial optimization: the bottleneck of a…
Flows in Networks III: The Circulation TheoremTextbook
Many questions in operations research and combinatorics ask whether a system of linear inequalities on a network has a solution: can the demands at a set of warehouses be met from the supplies at a set of factories through roads of limited capacity; is there a nonnegative matrix with bounded entries whose row and column sums lie between given limits; can a…
Lectures on Modern Convex Optimization X: Complexity of the Ellipsoid MethodTextbook
A convex program whose objective and feasible set are known only through oracles, routines that answer queries about one point at a time, can still be solved to any prescribed accuracy with a number of queries bounded in advance. The ellipsoid method is the classical algorithm that achieves this. It was introduced for convex minimization by Yudin and…
Lectures on Modern Convex Optimization XI: Primal-Dual Path-Following for Semidefinite ProgrammingTextbook
Semidefinite programming (SDP), the optimization of a linear function over the intersection of an affine subspace with the cone of positive semidefinite matrices, is the workhorse behind relaxations in combinatorial optimization, robust optimization and control. Its practical and theoretical tractability rests on interior point methods: algorithms that…
Lectures on Modern Convex Optimization VIII: The Matrix Cube TheoremTextbook
Many questions in robust control and robust optimization reduce to one test: does a whole family of symmetric matrices, generated by perturbing a nominal matrix along several directions at once, stay positive semidefinite? A linear system whose coefficients are only known to lie in intervals is a typical case. Showing that one quadratic Lyapunov function…
Lectures on Modern Convex Optimization VII: The S-Lemma with Two Quadratic ConstraintsTextbook
A homogeneous quadratic inequality xTBx≥0 may hold at every point where other quadratic inequalities xTAix≥0 hold. Deciding when this happens is the quadratic analogue of the question the Farkas lemma answers for linear inequalities. It is the core of robust optimization with ellipsoidal uncertainty, of absolute stability in control (where it is…
Lectures on Modern Convex Optimization IV: The Compliance of a Truss Is Conic Quadratic RepresentableTextbook
Truss topology design asks for the stiffest elastic bar construction that can be built from a given set of potential bars with a given amount of material. It is one of the oldest test cases of structural optimization (Bendsøe and Sigmund, Topology Optimization, Springer 2003) and one of the main applications in Ben-Tal and Nemirovski's Lectures on Modern…
Lectures on Modern Convex Optimization II: The Conic Duality TheoremTextbook
Linear, second-order cone and semidefinite programming are three instances of one format: minimize a linear objective subject to the requirement that an affine image of the decision vector lie in a fixed convex cone. Ben-Tal and Nemirovski's Lectures on Modern Convex Optimization (SIAM 2001) builds its whole treatment of modelling and algorithms on this coni…
Lectures on Modern Convex Optimization III: The Convex Hull of Conic Quadratic Representable SetsTextbook
Conic quadratic programs (second-order cone programs) minimize a linear objective subject to finitely many constraints of the form ∥Dx−d∥2≤pTx−q. They are solved by interior-point methods in polynomial time, and a large share of convex models in engineering, statistics and robust optimization can be rewritten in this form. Whether a given convex…
Lectures on Modern Convex Optimization I: The Linear Programming Duality TheoremTextbook
Every linear program comes with a second linear program, its dual, whose feasible points certify lower bounds on the first program's optimal value. The duality theorem says that these certificates are complete: the best bound equals the optimal value whenever either is finite. It is the reason an LP solver can return a proof of optimality alongside a…
Partial Completion as a Nonprofit Strategy: Under a Budget Constraint, the Optimal Variety and Completion Levels Follow Three Budget Regimes and Both Rise With the BudgetResearch Paper
A nonprofit choosing how to serve people with different needs may have two ways to use an additional dollar: offer more product variants, or deliver a larger fraction of each product. Beneficiaries can sometimes finish an incomplete product themselves, but doing so takes effort. Zhang, Atasu and Ramachandran study this choice for services such as…