Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

The OR Formalization Drive

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.

3569 completed missions

Missions

2476–2500 of 3569
Open1243Completed3569All4812
🏆Completed
Linear algebraMarkov ChainNumerical Analysis+3·Captain: Shuze Chen

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…

8 thms2 active usersReviewed
🏆Completed
Linear algebraMarkov ChainOperations Research+2·Captain: Shuze Chen

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…

12 thms2 active usersReviewed
🏆Completed
Linear algebraMarkov ChainNumerical Analysis+3·Captain: Shuze Chen

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…

6 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: Shuze Chen

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…

9 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: Shuze Chen

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\pi_n = \pi_0 R^nπn​=π0​Rn (Neuts, Matrix-G…

20 thms2 active usersReviewed
🏆Completed
Linear algebraMarkov ChainOperations Research+2·Captain: Shuze Chen

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 TTT of the state space, and describe what happens in between through…

10 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: Shuze Chen

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…

10 thms2 active usersReviewed
🏆Completed
Linear algebraMarkov ChainOperations Research+2·Captain: Shuze Chen

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,∞)[0,\infty)[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 function R(x)R(x)R(x), the expected number of…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

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⁡Q\|C_{\max}Q∥Cmax​, the minimum makespan problem on uniform parallel machines. It is strongly NP-hard, so the…

15 thms2 active usersReviewed
🏆Completed
Linear algebraMarkov ChainOperations Research+2·Captain: Shuze Chen

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…

11 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization+2·Captain: Shuze Chen

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…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research·Captain: Shuze Chen

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 nnn nodes there are n(n−1)/2n(n-1)/2n(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…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research·Captain: Shuze Chen

Flows in Networks VI: Zero-One Matrices with Zero TraceTextbook

An m×nm \times nm×n matrix of 000's and 111's is the incidence matrix of mmm sets against nnn elements, or the adjacency matrix of a bipartite graph, or, when m=nm = nm=n, the adjacency matrix of a directed graph on nnn 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…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: Shuze Chen

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…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization+1·Captain: Shuze Chen

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…

11 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization+1·Captain: Shuze Chen

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…

8 thms2 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOperations Research+1·Captain: Shuze Chen

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…

6 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraNumerical Analysis+2·Captain: Shuze Chen

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…

9 thms2 active usersReviewed
🏆Completed
Control TheoryConvex OptimizationOperations Research+1·Captain: Shuze Chen

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…

10 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Lectures on Modern Convex Optimization VII: The S-Lemma with Two Quadratic ConstraintsTextbook

A homogeneous quadratic inequality xTBx≥0x^TBx \ge 0xTBx≥0 may hold at every point where other quadratic inequalities xTAix≥0x^TA_ix \ge 0xTAi​x≥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…

10 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

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…

9 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

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…

9 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

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\|Dx - d\|_2 \le p^Tx - q∥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…

8 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research+1·Captain: Shuze Chen

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…

11 thms2 active usersReviewed
🏆Completed
EconomicsOperations ResearchOptimization·Captain: mikedeng1

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…

8 thms2 active usersReviewed
PreviousPage 100 of 143Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5262500
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR37275574
5NINickrobbins953290156
6VEvebis25800
7FIfizzyinc321735
8SHshivm17520
9KMkmehltretter821002265
10SCShuze Chen9455327

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me