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.

4812 missions

Missions

851–875 of 4812
Open1285Completed3527All4812
🏆Completed
Algorithmic Game TheoryLinear OptimizationOptimization·Captain: mikedeng1

Bimatrix Equilibrium Points and Mathematical Programming: If Z Is Non-Degenerate and uᵀMu ≥ 0, uᵀMu = 0 ⇒ Mu + Mᵀu = 0 for All u ≥ 0, a Non-Empty Z Has an Equilibrium PointResearch Paper

The linear complementarity problem asks, for a real square matrix MMM of order nnn and a vector q∈Rnq\in\mathbb R^nq∈Rn, for a vector zzz with

11 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryLinear OptimizationOperations Research·Captain: mikedeng1

Existence of Correlated Equilibria I: Every Finite Game Has a Correlated EquilibriumResearch Paper

In a finite game, a referee can recommend one action privately to each player according to a joint distribution. The recommendations may be correlated: learning one's own recommendation can convey information about the others'. A correlated equilibrium is a distribution for which no player gains, in expectation, by replacing a particular recommendation with…

8 thms4 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchProbability+1·Captain: mikedeng1

Subadditive Ergodic Theory 3: A Separable Continuous-Parameter Subadditive Process with E(Ω_I) < ∞ Has x₀ₜ/t → ξ with Probability One and in Mean, E(ξ) = γResearch Paper

Many random growth models attach a cost, distance, or accumulated quantity to each time interval. If the quantity over a long interval is at most the sum over two adjacent intervals, it is subadditive. A stable rate over long intervals is useful even when the underlying random system does not have a simple independent-increment description. Kingman's 1973…

8 thms4 active usersReviewed
🏆Completed
CombinatoricsMarkov ChainProbability+1·Captain: mikedeng1

On the Generalized “Birth-and-Death” Process 2: For Constant Rates λ₀ ≤ μ₀ the Cumulative Population M_∞ Has Law Q_M = ((λ₀+μ₀)/2λ₀)(2M)! x^M/(2^{2M}(M!)²(2M−1))Research Paper

A birth-and-death process describes a population in which each individual independently gives birth and dies at given rates. Kendall's 1948 paper (doi:10.1214/aoms/1177730285) solved the process with arbitrary time-dependent rates and, in its §4, introduced a second random variable alongside the population size: the cumulative population MtM_tMt​, the number of…

5 thms4 active usersReviewed
🏆Completed
CombinatoricsDiscrete GeometryGroup Theory·Captain: mikedeng1

Some Polyhedra Related to Combinatorial Problems IV: In a Group All of Whose Elements Have Order 2, or All Order 3, the Irreducible Solutions of the Group Equation Are Exactly the VerticesResearch Paper

Every pure integer program min⁡{c⋅x:Ax=b, x≥0 integer}\min\{c\cdot x : Ax = b,\ x \ge 0 \text{ integer}\}min{c⋅x:Ax=b, x≥0 integer} can be relaxed, by dropping the nonnegativity of the basic variables of an optimal linear-programming basis, to a problem over a finite Abelian group: find nonnegative integers t(g)t(g)t(g), one for each nonzero group element, with ∑t(g)⋅g=g0\sum t(g)\cdot g = g_0∑t(g)⋅g=g0​. R. E. Gomory's 1969 paper Some…

8 thms4 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Global Convergence Properties of Conjugate Gradient Methods for Optimization I: Conjugate Gradient Methods with |β_k| ≤ β_k^FR Are Globally Convergent under Strong Wolfe Line SearchesResearch Paper

Nonlinear conjugate gradient methods minimize a smooth function fff of nnn variables using only function values, gradients and a few vectors of storage. They are the method of choice when nnn is so large that quasi-Newton matrices cannot be stored, and they remain a standard component of large-scale optimization software. Their convergence theory is delicate: the…

5 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

The Computational Algorithm for the Parametric Objective Function: The Basis Entered at a Characteristic Value λ̄ Is Optimal on an Interval Whose Left Endpoint Is λ̄Research Paper

A linear program often has two objectives that pull in different directions, for example cost and risk, or two policy goals whose relative weight is a matter of judgment. Gass and Saaty (NRLQ 1955) put the question in its simplest form: let every cost coefficient be an affine function dj+λdj′d_j + \lambda d'_jdj​+λdj′​ of one real parameter λ\lambdaλ, and find, for every…

17 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationMarkov Chain+2·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems V: Average Reward — an Extreme Optimal Solution of the Multichain Linear Program Yields a Pure Stationary Average Optimal PolicyTextbook

A Markov decision problem with the average reward criterion asks for a policy that maximises the long-run reward per period of a controlled finite Markov chain. It is the standard model for repeated operational decisions with no natural horizon: inventory replenishment, machine maintenance, queue admission and routing. For finitely many states and actions,…

17 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationMarkov Chain+1·Captain: mikedeng1

Linear Programming and Markov Decision Chains 1: A Pure Policy Read Off a Simplex-Optimal Solution of One Dual LP Is Average Optimal in Every Finite Multichain MDPResearch Paper

A Markov decision chain with finitely many states and actions is the basic model of sequential decision making under uncertainty in operations research. Inventory control, maintenance, queueing control and many other problems reduce to it. Under the average reward criterion the decision maker optimizes the long-run reward per period. For the discounted…

17 thms4 active usersReviewed
🏆Completed
CombinatoricsComputational GeometryDiscrete Geometry+1·Captain: mikedeng1

A Combinatorial Theorem in Plane Geometry: Every n-Triangulation Can Be Partitioned into at Most ⌊n/3⌋ FansResearch Paper

In a conversation reported by Chvátal, Victor Klee asked for the smallest number f(n)f(n)f(n) such that every region bounded by a simple closed nnn-gon is dominated by f(n)f(n)f(n) points: every point of the region sees one of them along a segment inside the region. In the picturesque language that gave the problem its name, f(n)f(n)f(n) is the number of guards needed to watch any ar…

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

Deterministic Equivalents for Optimizing and Satisficing under Chance Constraints 2: The Fractional P-Model Program (38) Has the Same Supremum as the Convex Program (39)Research Paper

A chance constraint limits the probability of violating a requirement rather than requiring that requirement to hold for every realization of uncertain data. Charnes and Cooper developed deterministic optimization problems for several ways of judging decisions under such constraints. Their P model gives a satisficing objective: increase the probability of…

6 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningOperations Research+1·Captain: mikedeng1

Stable Function Approximation in Dynamic Programming I: In a Discounted Finite MDP, Value Iteration Through an Averager Converges to V₀ with ‖V₀ − V*‖ ≤ 2γε/(1 − γ)Research Paper

Value iteration computes the optimal value function of a Markov decision process by applying the dynamic programming backup to every state until the values stop changing. When the state space is too large for a lookup table, practitioners replace the table by a function approximator: after each backup, the new values are computed only at a sample of states…

8 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

An Additive Algorithm for Solving Linear Programs with Zero-One Variables: In Finitely Many Iterations the Additive Algorithm Yields an Optimal Solution or Proves InfeasibilityResearch Paper

Binary decisions arise when a variable records whether a project is selected, a facility is opened, or an action is taken. Linear constraints then describe the resources or conditions those choices must satisfy. Egon Balas's 1965 paper gives a direct algorithm for a finite linear program with zero-one variables: it begins with all variables at zero, adds…

10 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryFunctional AnalysisOperations Research+1·Captain: mikedeng1

A Variational Inequality Formulation of the Dynamic Network User Equilibrium Problem I: Route-Departure Equilibria Are Exactly the Solutions of the Path-Integral Variational InequalityResearch Paper

Commuters choose not only a route but also a departure time, trading travel delay against the penalty of arriving early or late. Static traffic assignment, in the tradition of Wardrop's user-equilibrium principle, ignores the time dimension; dynamic traffic assignment adds it, and its central modelling question is what "equilibrium" means when flows, delays…

11 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

Matching, Euler Tours and the Chinese Postman IV: Every Connected, Even, Symmetric Mixed Graph Has an Euler TourResearch Paper

A postman, a snowplough or a street sweeper must traverse every street of a district and return to the depot. When some streets are one-way, the street network is a mixed graph: some edges are directed and must be traversed in a prescribed direction, the others are undirected and may be traversed either way. The first question about such a route is whether…

7 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

Paths, Trees, and Flowers I: Matching-Duality Theorem — the Maximum Cardinality of a Matching Equals the Minimum Capacity-Sum of an Odd-Set CoverResearch Paper

A matching in a graph is a set of edges no two of which share a vertex. Finding a matching of maximum cardinality is one of the basic problems of combinatorial optimization: it models pairing tasks (workers to shifts, kidney donors to recipients, players to rounds), it is a subroutine of algorithms for the travelling salesman and Chinese postman problems,…

16 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows: With No Negative Marginal Cost Column, the Set Covering LP Is Optimal and Bounds the VRPTW Optimum from BelowResearch Paper

The vehicle routing problem with time windows (VRPTW) asks for minimum-cost routes from a central depot that serve every customer exactly once, respecting vehicle capacity and a time interval in which each customer's service must begin. It models school bus routing, parcel and retail distribution, and dial-a-ride services. Desrochers, Desrosiers and Solomon…

13 thms4 active usersReviewed
🏆Completed
Information TheoryOptimizationProbability+1·Captain: mikedeng1

I-Divergence Geometry of Probability Distributions and Minimization Problems 1: Cyclic I-Projections onto Linear Sets of a Finite Space Converge to the I-Projection onto Their IntersectionResearch Paper

Fitting a probability distribution to prescribed margins or moments is a basic task in statistics and information theory. Starting from a reference distribution, one can enforce one constraint at a time by choosing the closest distribution in I-divergence, then cycle through the constraints. In a contingency table this procedure is iterative proportional…

14 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Scheduling of Vehicles from a Central Depot to a Number of Delivery Points: The Savings Procedure Always Ends in a Feasible Truck Allocation Whose Mileage Is the Initial Less the Linked SavingsResearch Paper

Delivering goods from one depot to many customers with a fleet of trucks is the vehicle routing problem. Dantzig and Ramser formulated it in 1959 as the "truck dispatching problem" (Management Sci. 6 (1959), doi:10.1287/mnsc.6.1.80). Five years later Clarke and Wright proposed the savings procedure (Oper. Res. 12 (1964), 568–581, doi:10.1287/opre.12.4.568):…

12 thms4 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions: PMD Attains f(xⁿ) − f(u) ≤ σₙ⁻¹D_ψ(u, x⁰) and Its Iterates Converge to a MinimizerResearch Paper

Convex minimization often has a simple objective but no useful closed form for its minimizer. A proximal method replaces one difficult minimization by a sequence of regularized minimizations. The familiar quadratic regularizer treats all directions through a Euclidean norm. In applications with nonnegative variables, entropy-like geometry can be more…

9 thms4 active usersReviewed
🏆Completed
Complexity TheoryDynamic ProgrammingOperations Research+1·Captain: mikedeng1

The Complexity of Markov Decision Processes I: A Boolean Circuit Is True Iff Its Finite-Horizon Markov Decision Process Has Optimal Expected Cost ZeroResearch Paper

Markov decision processes are the standard model of sequential decision making under uncertainty in operations research, control and artificial intelligence. Their finite-horizon, discounted and average-cost versions are all solvable in polynomial time, by dynamic programming or linear programming. Papadimitriou and Tsitsiklis (The Complexity of Markov…

8 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingGraph TheoryOperations Research+1·Captain: mikedeng1

The Complexity of Markov Decision Processes III: The Optimal Discounted Cost of a Deterministic Process Is the Least Discounted Cost of a SigmaResearch Paper

A Markov decision process with finitely many states and decisions, a discount factor β∈(0,1)\beta\in(0,1)β∈(0,1) and the objective of minimizing expected discounted cost is the basic model of sequential decision making in operations research and reinforcement learning. It is solvable in polynomial time by linear programming. Papadimitriou and Tsitsiklis (Math. Oper. Res.…

7 thms4 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Poisson Approximation for Dependent Trials 1: For φ-Mixing Bernoulli Trials, |Eh(W) − 𝒫_λh| ≤ 6 min(λ^{−1/2}, 1)[Var W − λ + 2(2m+1)Σp_i² + 4(λ+1)nφ(m+1)]Research Paper

A sum of many rare events is approximately Poisson. For independent Bernoulli trials this is the classical law of small numbers, and its quantitative form goes back to Prohorov (1953) and Le Cam (1960): if X1,…,XnX_1,\dots,X_nX1​,…,Xn​ are independent with P(Xi=1)=piP(X_i=1)=p_iP(Xi​=1)=pi​, then the law of W=∑iXiW=\sum_i X_iW=∑i​Xi​ is close to the Poisson law with mean λ=∑ipi\lambda=\sum_i p_iλ=∑i​pi​, with an error…

19 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Assortment Optimization under Variants of the Nested Logit Model 6: For δ > 1, the Powers-of-δ LP Optimum Scaled by (δ^(2γ̄+1), δ^(γ̄+1)) Is Feasible for the Full LPResearch Paper

Assortment optimization asks which products a retailer should offer when customers choose among the offered products according to a probabilistic choice model, so as to maximize expected revenue. Under the nested logit model the products are grouped into nests: a customer first picks a nest, then a product inside it. The model is the standard relaxation of…

21 thms4 active users
🏆Completed
Linear OptimizationProbabilityStatistics·Captain: mikedeng1

Optimal Estimation of Executive Compensation by Linear Programming II: LP Estimates Are Consistent When the True Optimum Is Unique and NondegenerateResearch Paper

In 1955 Charnes, Cooper and Ferguson proposed to estimate the weights of an executive compensation scheme by linear programming instead of least squares: the weights minimise a sum of absolute deviations subject to ranking, ceiling and floor constraints, which is a linear program. The coefficients of that program are not known exactly. They are averages of…

7 thms4 active usersReviewed
PreviousPage 35 of 193Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5162497
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36515432
5NINickrobbins953286155
6VEvebis25800
7FIfizzyinc321725
8SHshivm17490
9SCShuze Chen9455324
10KMkmehltretter82895261

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