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

2276–2300 of 4812
Open1247Completed3565All4812
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

On the Relation Between Integer and Noninteger Solutions to Linear Programs: Deep in the Optimal-Basis Cone, z₂(b) = z₁(b) + φ(b) and the Group Problem Gives an Integer OptimumResearch Paper

An integer program is a linear program whose variables must take integer values. Its linear relaxation can be solved efficiently, while the integer program itself is NP-hard in general, so a recurring question in integer programming is how much the optimal solution of the relaxation says about the integer optimum. Simple rounding of the fractional optimum…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Residual Life Time at Great Age 1: Every Nondegenerate Limit Law of the Normed Residual Life Time Is of Type Π, Π_γ, Γ_α or Γ_{γ,α}Research Paper

A component with a random lifetime XXX that has survived to age ttt still has a random residual life time X−tX - tX−t. Reliability engineering, actuarial science and the statistics of exceedances over high thresholds all ask how the conditional law of X−tX - tX−t given X>tX > tX>t behaves when the age ttt is large. If XXX is exponential, the residual life has the same law at every…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Simulation Output Analysis Using Standardized Time Series 1: For Every g in the Class 𝓜, (Ȳₙ(1) − μ)/g(Ȳₙ) ⇒ B(1)/g(B) Under the FCLT (2.1)Research Paper

A discrete-event simulation of a queue, an inventory system or a communication network produces an output process Y={Y(t):t≥0}Y = \{Y(t) : t \ge 0\}Y={Y(t):t≥0}, and the quantity of interest is usually its steady-state mean μ\muμ, the long-run average of YYY. The natural estimator is the time average Yˉn(1)=1n∫0nY(s) ds\bar Y_n(1) = \frac1n\int_0^n Y(s)\,dsYˉn​(1)=n1​∫0n​Y(s)ds of a run of length nnn. A confidence interval…

6 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research·Captain: mikedeng1

A Suggested Computation for Maximal Multi-Commodity Network Flows: With Nonnegative Simplex Multipliers, Shortest-Chain Labels Prove the Arc-Chain Basis Optimal or Find an Entering ChainResearch Paper

The maximal multi-commodity flow problem asks how much total flow several commodities, each travelling from its own sources to its own sinks, can send through a network whose arcs have shared capacities. It arises in communication and transportation planning: Kalaba and Juncosa's 1956 study of communication networks (Management Science 3(1)) leads to linear…

12 thms3 active usersReviewed
🏆Completed
AnalysisOperations Research·Captain: mikedeng1

A Variational Inequality Formulation of the Dynamic Network User Equilibrium Problem II: Under Linear Arc Delay αx(t) + β the Arc Exit Time Is Strictly Increasing (FIFO Holds)Research Paper

Dynamic traffic assignment models how commuters choose routes and departure times when travel times change over the day. In the model of Friesz, Bernstein, Smith, Tobin and Wie (Oper. Res. 41 (1993)), the time to traverse a path is built recursively from arc exit-time functions: a vehicle that enters an arc at time ttt leaves it at time τ(t)\tau(t)τ(t). The…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimal TransportProbability+1·Captain: mikedeng1

Data-Driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations III: Asymptotic Consistency of Wasserstein Robust SolutionsResearch Paper

Many decisions in operations research and machine learning minimize an expected cost EP[h(x,ξ)]\mathbb E^{P}[h(x,\xi)]EP[h(x,ξ)] whose distribution PPP is unknown and is seen only through NNN independent samples. The sample-average approximation replaces PPP by the empirical distribution and is known to produce decisions with poor out-of-sample performance when NNN is small. Distributi…

15 thms3 active usersReviewed
🏆Completed
Linear algebraMachine LearningMarkov Chain+1·Captain: mikedeng1

Learning to Predict by the Methods of Temporal Differences: Linear TD(0) Converges in Expected Value to the Ideal Predictions on Absorbing Markov ChainsResearch Paper

Temporal-difference (TD) methods learn to predict an eventual outcome from the differences between successive predictions rather than from the difference between each prediction and the final outcome. Sutton's 1988 paper Learning to predict by the methods of temporal differences introduced the TD(λ\lambdaλ) family and gave the first convergence proof for a TD…

24 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimal Transport+1·Captain: mikedeng1

Data-Driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations II: Worst-Case Distributions from a Finite Convex ProgramResearch Paper

In data-driven stochastic optimization a decision maker knows the distribution of an uncertain parameter ξ\xiξ only through NNN samples ξ^1,…,ξ^N\hat\xi_1,\dots,\hat\xi_Nξ^​1​,…,ξ^​N​. Wasserstein distributionally robust optimization hedges against this ignorance by evaluating a loss ℓ\ellℓ under the worst distribution in a ball, measured in the Wasserstein metric, around the…

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

Perfect Equilibrium in a Bargaining Model: The Perfect Equilibrium Partitions Are the Nonempty Closed Intervals A = Δ₁ and B = Δ₂ = A − εResearch Paper

Alternating-offer bargaining asks how an agreement is selected when two people can keep making proposals until one accepts. A prediction based only on behavior at the start may rely on threats that would no longer be sensible after a rejection. Ariel Rubinstein's 1982 paper studies strategies after every possible sequence of offers and gives a…

14 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimal Transport+1·Captain: mikedeng1

Data-Driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations I: Wasserstein Worst-Case Expectations as Finite Convex ProgramsResearch Paper

A decision maker who must minimize an expected cost EP[h(x,ξ)]\mathbb E^{\mathbb P}[h(x,\xi)]EP[h(x,ξ)] rarely knows the distribution P\mathbb PP of the uncertain parameter ξ\xiξ; usually only NNN samples ξ^1,…,ξ^N\hat\xi_1,\dots,\hat\xi_Nξ^​1​,…,ξ^​N​ are available. Replacing P\mathbb PP by the empirical distribution (sample average approximation) tends to produce decisions that perform poorly out of…

17 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationOperations Research+1·Captain: mikedeng1

On the Convergence of Stochastic Dual Dynamic Programming and Related Methods: DOASA Reaches an Optimal Policy in Finitely Many Iterations Almost SurelyResearch Paper

Stochastic dual dynamic programming (SDDP), introduced by Pereira and Pinto in 1991, is the standard method for multistage stochastic linear programs with many stages, such as hydro-thermal scheduling and long-term energy planning. It approximates each stage's expected future cost from below by the maximum of finitely many linear functions (cuts), built…

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

Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions 2: Geometric Convergence Rate of the Random Directions Algorithm to UniformResearch Paper

Generating points uniformly distributed over a bounded region S⊆RnS\subseteq\mathbb R^nS⊆Rn is a basic subroutine in Monte Carlo integration, in estimating the volume of a region, in randomized search for optimization, and in identifying redundant constraints of mathematical programs. When SSS is given only implicitly, for instance by a system of inequalities, the…

10 thms3 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Poisson Approximation for Dependent Trials 2: For φ-Mixing Bernoulli Trials, an Order-λ⁻¹ Bound on |Eh(W) − 𝒫_λh| in Var W − λ + 2(2m+1)Σp_i² and nφ(m+1)Research Paper

The number of successes in many rare trials is approximately Poisson. For independent trials the quality of that approximation was quantified by Le Cam in 1960: if X1,…,XnX_1,\dots,X_nX1​,…,Xn​ are independent Bernoulli variables with P(Xi=1)=piP(X_i=1)=p_iP(Xi​=1)=pi​, W=∑iXiW=\sum_i X_iW=∑i​Xi​ and λ=∑ipi\lambda=\sum_i p_iλ=∑i​pi​, the total variation distance between the law of WWW and the Poisson law with mean λ\lambdaλ is…

22 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions 1: Symmetric Mixing Algorithms Converge to the Uniform Distribution from Every Starting PointResearch Paper

Sampling uniformly from a bounded region can be difficult when direct transformation of a familiar random variable is unavailable and rejection sampling spends most of its trials outside the region. Robert L. Smith studied procedures that move within the region: from the current point, choose a direction, form the line set through that point inside the…

8 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

On the Convergence of Interior-Reflective Newton Methods for Nonlinear Minimization Subject to Bounds 1: The Interior-Reflective Line Search Algorithm Drives D_k²g_k to ZeroResearch Paper

Minimizing a smooth function subject to simple bounds on the variables, l≤x≤ul\le x\le ul≤x≤u, is one of the most common problems in nonlinear optimization: it arises on its own (nonnegativity constraints, box-constrained least squares, parameter estimation with physical ranges) and as the subproblem of augmented Lagrangian and penalty methods. The classical…

8 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Optimal Auction Design: Giving the Object to a Bidder with the Highest Priority Level c̄ᵢ(tᵢ) ≥ t₀ and Charging (6.8) Is an Optimal Auction MechanismResearch Paper

A seller with one indivisible object must decide whether to keep it or transfer it to one of several bidders whose values she does not observe. The allocation and the payment rule affect what bidders choose to report. Myerson's 1981 paper identifies a revenue-maximizing rule when bidders' private value estimates are independent, their densities are…

13 thms3 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Poisson Approximation for Dependent Trials 3: For Independent Trials with max p_i ≤ λ/2, |Eh(W) − 𝒫_λh + (Σp_i²)𝒫_λU_λh| ≤ (24 + 96√2)λ⁻¹Σp_i³Research Paper

The number of successes in many rare, roughly independent trials is approximately Poisson. This law of small numbers is used for counts of rare events in reliability, insurance, epidemiology, queueing and random combinatorics. A quantitative version says how large the error is. For independent Bernoulli trials with success probabilities p1,…,pnp_1,\dots,p_np1​,…,pn​ and …

16 thms3 active usersReviewed
🏆Completed
CombinatoricsDynamic ProgrammingGraph Theory+1·Captain: mikedeng1

The Complexity of Markov Decision Processes IV: In a Deterministic Process a Cheapest T-Arc Walk Is a Walk of Fewer Than n³ Arcs Plus One Repeated CycleResearch Paper

Finite-horizon Markov decision processes ask which decisions minimize accumulated cost over a specified number of stages. In a stationary process, the same costs and transitions apply at every stage. This compact input can describe a horizon TTT much larger than the state set, so a method that processes all TTT stages one by one may take time exponential in the…

6 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

The Bargaining Problem: The Nash Product Maximizer Is the Unique Solution Satisfying Invariance, Symmetry, IIA and Pareto EfficiencyResearch Paper

Two parties who can cooperate for mutual benefit must still agree on how to share the benefit. In The Bargaining Problem (Econometrica, 1950) John Nash asked which agreement two rational bargainers of equal skill should reach. His answer is not a model of haggling: it is a list of conditions any reasonable rule should satisfy, together with a proof that…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability+1·Captain: mikedeng1

An Optimal Algorithm for On-line Bipartite Matching 2: No Randomized On-line Algorithm Guarantees an Expected Matching Larger Than n(1 − 1/e) + o(n)Research Paper

An online matching algorithm must commit to each assignment when a request arrives, before it sees later requests. This limitation arises whenever waiting for the full instance is impossible: an available resource can be assigned to a current request or saved for an unknown future request. The quality of the assignment is measured by how many requests can…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Wait-and-Judge Scenario Optimization 2: Over Generic Sets, P^N{V(x_N) > ε(s_N)} ≤ γ*, the Least ξ(1) over Degree-N Polynomials Feasible for (31)Research Paper

A solution of a scenario optimization program is chosen after observing finitely many uncertain constraints. Its future reliability depends on constraints that were not sampled. The usual advance question asks how many samples are needed to make every output reliable. Campi and Garatti instead ask what can be certified after solving the program, when the…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Supply Chain Coordination with Contracts VI: With a Forecast Update, Buy-Back Terms with w₁ − w₂ + λc₂ = λc₁ Give the Retailer λΩ₁(q₁) and a Lower Period-2 Margin w₂ − c₂ < w₁ − c₁Textbook

A newsvendor retailer who may order twice faces a tradeoff. Ordering late lets the retailer use a better demand forecast. Ordering early lets the supplier produce more cheaply, with longer procurement lead times and no overtime labor. Fisher and Raman (1996) document such forecast improvements between ordering epochs in fashion apparel. A decentralized…

12 thms3 active usersReviewed
🏆Completed
Discrete GeometryLinear OptimizationNumber Theory+1·Captain: mikedeng1

Integer Programming with a Fixed Number of Variables 1: If B(p,r) ⊂ τK ⊂ B(p,R) with R/r ≤ c₁ and τK Misses the Lattice, Fewer Than 1 + c₁c₂√n Lattice Hyperplanes H + kbₙ Meet B(p,R)Research Paper

The integer linear programming feasibility problem asks, for an integer m×nm\times nm×n matrix AAA and b∈Zmb\in\mathbb Z^mb∈Zm, whether some x∈Znx\in\mathbb Z^nx∈Zn satisfies Ax≤bAx\le bAx≤b. It is NP-complete, so no algorithm polynomial in the length of the data is expected. H. W. Lenstra, Jr. (Math. Oper. Res. 8 (1983) 538–548) showed that the picture changes when the number of…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Supply Chain Coordination with Contracts VII: In the Single-Location Base-Stock Model the Transfers t_I = (1 − λ)h_r, t_B = β_r − λβ Make the Retailer's Cost λc(s_r)Textbook

A retailer can keep too little inventory even when its own stocking decision is optimal. In the single-location model of Cachon, Supply Chain Coordination with Contracts (2003), the supplier suffers a cost when the retailer has backorders, but the retailer does not bear that part of the cost. The supplier and retailer therefore prefer different base-stock…

12 thms3 active usersReviewed
🏆Completed
Discrete GeometryLinear OptimizationOperations Research·Captain: mikedeng1

On Linear Characterizations of Combinatorial Optimization Problems III: Zero-One and Integer-Programming-Type Problems Have Small Facial DescriptionsResearch Paper

Many discrete optimization problems can be described by linear inequalities, even when their feasible solutions are integer vectors. A linear description lets one study the geometry of the feasible set and connect combinatorial methods with linear programming. The number of inequalities may be large, so a more basic question is whether each inequality needs…

6 thms3 active usersReviewed
PreviousPage 92 of 193Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5259500
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36735482
5NINickrobbins953290156
6VEvebis25800
7FIfizzyinc321735
8SHshivm17520
9KMkmehltretter82995263
10SCShuze Chen9455326

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