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.

3554 completed missions

Missions

2151–2175 of 3554
Open1258Completed3554All4812
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research+1·Captain: Shuze Chen

Discrete Convex Analysis XVIII: Integral Convexity of Minimizer SetsTextbook

A classical convex function's global minimality is equivalent to its local minimality — the single fact that makes convex optimization tractable, since checking a small neighborhood suffices to certify a global guarantee. The discrete analogue is not automatic: a function on the integer lattice can fail to have any well-behaved "local" notion at all, and…

28 thms3 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research+1·Captain: Shuze Chen

Discrete Convex Analysis XVII: Fenchel Duality and Linear-Programming IntegralityTextbook

Duality is the organizing principle of convex optimization: a minimization problem's optimal value equals a maximization problem's optimal value, and this coincidence, rather than being a lucky accident, follows from a separating-hyperplane argument that applies whenever the two problems' feasible regions are shaped compatibly enough. Werner Fenchel…

37 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: Shuze Chen

Markov Decision Processes VII: Consumption-Investment Problems and Regime SwitchingTextbook

Real investors do not merely accumulate wealth for a single terminal payoff; they consume along the way, and the market they invest in is rarely a single fixed statistical regime for years at a time — bull and bear markets, business cycles, and volatility regimes shift the distribution of returns. Bäuerle and Rieder's §4.3 extends the terminal-wealth theory…

16 thms3 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryOperations Research+3·Captain: mikedeng1

Maximizing Non-Monotone Submodular Functions V: Beating 1/2 for Symmetric Functions Requires Exponentially Many Value QueriesResearch Paper

Maximizing a nonnegative submodular set function without constraints contains Max Cut, Max Directed Cut and facility-location problems as special cases. In the value-oracle model an algorithm knows nothing about the function except the values f(S)f(S)f(S) of the sets SSS it queries, and it is judged by the number of queries it makes. Feige, Mirrokni and Vondrák (SIAM…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsConvex OptimizationDiscrete Geometry+2·Captain: mikedeng1

Lifts of Convex Sets and Cone Factorizations II: Antichain and Face-Count Lower Bounds on the Nonnegative Rank of a PolytopeResearch Paper

Many polytopes that arise in combinatorial optimization, such as the matching, cut, stable set and travelling salesman polytopes, have exponentially many facets, yet some of them can be written as the linear projection of a polyhedron with far fewer facets. The smallest number of facets of such a lift decides whether the polytope admits a compact…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+2·Captain: mikedeng1

Maximizing Non-Monotone Submodular Functions IV: Smooth Local Search Achieves 2/5 of the OptimumResearch Paper

Many optimization problems ask for a subset of a finite ground set that maximizes a submodular function, a set function with diminishing marginal returns. Max Cut and Max Directed Cut in graphs, facility location with fixed costs, and the maximization of mutual information or entropy of a subset of random variables are all of this form. Unlike the monotone…

14 thms3 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryLinear Optimization+2·Captain: mikedeng1

On Polyhedral Approximations of the Second-Order Cone II: A Lower Bound on the Size of Polyhedral ApproximationsResearch Paper

A conic quadratic program minimizes a linear objective subject to constraints of the form ∥Aℓx−bℓ∥2≤cℓTx−dℓ\|A_\ell x-b_\ell\|_2\le c_\ell^Tx-d_\ell∥Aℓ​x−bℓ​∥2​≤cℓT​x−dℓ​. Interior-point methods solve such programs in polynomial time, but around 2000 the available solvers handled far smaller instances than linear programming codes did. Ben-Tal and Nemirovski (Math. Oper. Res. 26(2), 2001) asked…

10 thms3 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisProbability+1·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix IV: Sample Bound for Hutchinson's Trace EstimatorResearch Paper

Many computations need the trace of a matrix AAA that is never formed explicitly and can only be applied to vectors: the trace of a matrix function such as trace(A−1)\mathrm{trace}(A^{-1})trace(A−1) or log⁡det⁡A=trace(log⁡A)\log\det A = \mathrm{trace}(\log A)logdetA=trace(logA) in statistics and lattice QCD, the Frobenius norm ∥B∥F2=trace(BTB)\|B\|_F^2 = \mathrm{trace}(B^TB)∥B∥F2​=trace(BTB) of an operator, or the number of triangles of a graph. The…

7 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: Shuze Chen

Markov Decision Processes II: Existence of Optimal Policies under Compactness and ContinuityTextbook

The finite-horizon theory of chunk 02a-model-bellman-equation (Bäuerle and Rieder's Theorem 2.3.8, the Structure Theorem) reduces the existence of an optimal policy and the validity of the Bellman equation to a single abstract hypothesis: the Structure Assumption (SAN), the existence of function classes IMn\mathrm{IM}_nIMn​ and decision-rule classes Δn\Delta_nΔn​ closed…

14 thms3 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisProbability+1·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix II: Exact Rank of a Projection Matrix from the Gaussian Trace EstimatorResearch Paper

Many matrices in scientific computing are available only implicitly: one can multiply a vector by AAA, for instance by solving a linear system or applying a matrix function, but the entries of AAA are never formed. Quantities such as the trace must then be estimated from a small number of matrix–vector products. Randomized trace estimators do exactly this: draw…

7 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Monotonic Solutions of Cooperative Games 1: For Five or More Players No Core Allocation Rule Is Coalitionally MonotonicResearch Paper

Cooperative games model the division of a jointly produced surplus, or a jointly incurred cost, among the participants of an enterprise: towns sharing a water supply system, divisions of a firm sharing overhead, members of a consortium sharing the savings of joint investment. In such applications allocations are rarely fixed once and for all. Costs and…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: Shuze Chen

Processing Networks XI: Maximal Stability of Workload-Weighted Task AllocationTextbook

Large-scale data-intensive computing splits a job into many small "map tasks," each of which must be assigned to one of thousands of general-purpose servers in a data center — the MapReduce paradigm introduced by Dean and Ghemawat (2008). Because a task's input data is stored on only a few of those servers, routing it to a server that already holds its data…

10 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

Optimal Policy for a Multi-Product, Dynamic, Nonstationary Inventory Problem: The Base Stock Ordering Policy Is OptimalResearch Paper

An inventory manager who stocks many products, faces random demand and pays ordering, holding and shortage costs must decide each period how much of each product to order. In general the optimal decision depends on the whole state and is found by solving a dynamic programme, which becomes impractical as the number of products grows. Myopic (or base stock)…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: Shuze Chen

Processing Networks X: Maximal Stability of Proportionally Fair ControlTextbook

Mission IX (09-proportional-fairness-core) formalized proportional fairness (PF) as a control policy and proved the technical core of its stability theory: under a load condition, the PF fluid model is stable (Theorem 10.5), via an entropy Lyapunov function that is genuinely not Lipschitz continuous — a departure from every other stability argument in J. G.…

13 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: mikedeng1

An Overview of Pricing Models for Revenue Management: Performance Guarantee of the Deterministic Price Heuristic in Periodic-Review PricingResearch Paper

Dynamic pricing under limited inventory is a core problem of revenue management: a seller holds C0C_0C0​ units of a perishable product (airline seats, hotel rooms, seasonal goods) and must choose prices over a finite selling horizon while demand is random and responds to price. The exactly optimal policy solves a stochastic dynamic program whose state is the…

9 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs: Binding Cuts Force Degenerate Descendant Problems in Nested DecompositionResearch Paper

Multistage stochastic linear programs model decisions taken in periods t=1,…,Tt = 1, \dots, Tt=1,…,T while a random vector ξt\xi_tξt​ is revealed period by period: production and capacity planning, energy scheduling, asset–liability management. With finitely many scenarios the problem is one very large linear program with a tree structure, and decomposition methods solve it…

5 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

Santa Claus Schedules Jobs on Unrelated Machines: The Configuration LP Has Integrality Gap at Most 33/17Research Paper

Scheduling jobs on unrelated machines so as to minimize the makespan (the time at which the last machine finishes) is one of the central problems of approximation algorithms. For the general problem, Lenstra, Shmoys and Tardos (1990) gave a 2-approximation and showed that no polynomial-time algorithm achieves a factor below 3/23/23/2 unless P = NP; closing the…

13 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: Shuze Chen

Processing Networks IX: Fluid Stability of the Proportionally Fair AllocationTextbook

Every control policy formalized so far in this series — HLSPS (mission VI), back-pressure/ max-weight (mission VIII) — allocates service effort to entire job classes as indivisible units. Proportional fairness takes a different starting point: it is a general-purpose recipe for dividing a shared, continuously divisible resource among competing demands,…

12 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryLinear OptimizationOperations Research·Captain: mikedeng1

The Assignment Game I: The Core 1: The Core Is the Set of Optimal Solutions of the Dual Assignment LPResearch Paper

A two-sided market in which each participant trades with at most one partner on the other side — houses and buyers, workers and firms, producers and consumers under exclusive bilateral contracts — is the setting of L. S. Shapley and M. Shubik's assignment game (Int. J. Game Theory 1 (1971) 111–130). Money is transferable, so the natural solution concept is…

6 thms3 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Learnability, Stability and Uniform Convergence I: A Problem Is Learnable if and only if It Admits a Uniform-RO Stable Universal AERMResearch Paper

In supervised binary classification, a hypothesis class is learnable if and only if it has uniform convergence, meaning that empirical risks converge to true risks uniformly over the class. When that holds, empirical risk minimisation (ERM) learns. This equivalence, due to Vapnik and Chervonenkis and extended to real-valued losses by Alon, Ben-David,…

12 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: Shuze Chen

Processing Networks V: Lyapunov Stability Criteria for Fluid ModelsTextbook

Mission III's Theorem 6.2 reduces SPN stability to a question about deterministic fluid model solutions: does every solution of a fixed system of equations get driven to the origin, uniformly in its starting size? Mission IV showed how to derive the extra, policy-specific equations a fluid model must satisfy. What remains is a method for proving that a…

15 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

On the Optimality of Generalized (s, S) Policies: A Generalized (s, S) Policy Is Optimal in Every Period of the Finite-Horizon Inventory ProblemResearch Paper

In a periodic-review inventory system a manager observes the stock level before ordering, decides how much to order, and then faces random demand. When ordering costs a fixed setup charge plus a constant price per unit, Scarf (1960) proved that an (s,S)(s,S)(s,S) policy is optimal in every period of a finite-horizon problem: order up to SSS when the stock falls below sss,…

17 thms3 active users
🏆Completed
Convex OptimizationFunctional AnalysisOperations Research+1·Captain: mikedeng1

A Dynamical Approach to an Inertial Forward-Backward Algorithm for Convex Minimization: The IFB Iterates Minimize the Objective and Converge Weakly to a MinimizerResearch Paper

Many problems in signal processing, statistics and operations research ask to minimize a sum Θ=Φ+Ψ\Theta = \Phi + \PsiΘ=Φ+Ψ of a nonsmooth convex term Φ\PhiΦ (a constraint indicator, an ℓ1\ell^1ℓ1 penalty) and a smooth term Ψ\PsiΨ. The standard method is the forward-backward (proximal-gradient) algorithm: an explicit gradient step on Ψ\PsiΨ followed by a proximal step on Φ\PhiΦ.…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Three Partition Refinement Algorithms 1: Distinguishing-Prefix Refinement Finds Every Distinguishing Prefix Within m′ Refinement StepsResearch Paper

Sorting a collection of strings in lexicographic order is a basic subroutine in compilers, string indexing, suffix sorting and the construction of tries. The classical method, due to Aho, Hopcroft and Ullman (The Design and Analysis of Computer Algorithms, 1974), is a multipass radix sort that processes the strings from the last position to the first and…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Dual Stochastic Dominance and Related Mean-Risk Models 1: Second-Degree Stochastic Dominance Is Dominance of Absolute Lorenz CurvesResearch Paper

Comparing uncertain outcomes is the basic problem of decision making under risk. Second-degree stochastic dominance (SSD) is the comparison that every risk-averse decision maker who prefers larger outcomes agrees with: XXX dominates YYY in this sense exactly when E U(X)≥E U(Y)\mathbb E\,U(X)\ge\mathbb E\,U(Y)EU(X)≥EU(Y) for every nondecreasing concave utility UUU for which the…

12 thms3 active usersReviewed
PreviousPage 87 of 143Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5227500
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36735478
5NINickrobbins953289156
6VEvebis25800
7FIfizzyinc321725
8SHshivm17500
9KMkmehltretter82958263
10SCShuze Chen9455324

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