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.

3527 completed missions

Missions

1801–1825 of 3527
Open1285Completed3527All4812
🏆Completed
Graph TheoryOperations ResearchProbability+1·Captain: mikedeng1

Loss Networks 3: If E e^{λX} < ∞ and 2E(X − C)⁺ < E(C − X)⁺, i.i.d. Loads on the Complete Graph Fit on Direct and Two-Edge Routes with Probability → 1Research Paper

Telephone and data networks are often fully connected at the core: every pair of switching centres has a direct trunk group, and a call that finds its direct trunk full may be alternatively routed over a two-link path through a third, tandem centre. Whether such a network can absorb fluctuations of demand without losing traffic depends on how the spare…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem 1: The Spanning-Tree Interchange Tour ψ* Is a Minimal Cost TourResearch Paper

The traveling salesman problem is NP-hard in general, so special cost structures under which it can be solved exactly in polynomial time are of lasting interest in combinatorial optimization and scheduling. One of the earliest and most cited such cases comes from sequencing on a machine whose condition is described by a single real number: a furnace…

15 thms3 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

On Tail Probabilities for Martingales 3: If E exp[−e(λ)W] ≤ e^{−λa} and E exp[−f(λ)W] ≥ e^{−λ(a+1)} for All λ ≥ 0, Then P{W < b} > ½ exp[−(½ + 2δ)a²/b]Research Paper

Freedman's inequality bounds the probability that a martingale with increments bounded above by 111 reaches a level aaa before its accumulated conditional variance exceeds bbb: the bound is exp⁡[−a2/2(a+b)]\exp[-a^2/2(a+b)]exp[−a2/2(a+b)] (D. A. Freedman, On Tail Probabilities for Martingales, Ann. Probab. 3 (1975) 100–118, Theorem (4.1), doi:10.1214/aop/1176996452). It is the standard tool…

14 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryComplexity TheoryLinear Optimization+1·Captain: mikedeng1

The Polynomial Hierarchy and a Simple Model for Competitive Analysis: Every Optimum of the (p+1)-Level Linear Game J'(F) Is Binary, with x(F) = 1 iff the Σ_p Sentence (3.3) HoldsResearch Paper

Multi-level programs model a hierarchy of decision makers: a leader commits to a decision, a follower optimises given it, a follower of the follower optimises given both, and so on. Bilevel programs are the standard model of Stackelberg competition, toll setting, network interdiction and many other leader–follower problems in operations research (Candler…

13 thms3 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOptimization·Captain: mikedeng1

A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite Element Approximation 1: For 0 < ρ < 2r, the Modified Dual Algorithm Converges Strongly to (v*, Av*)Research Paper

Many problems in mechanics and optimal control are posed as the minimization of a convex functional of the form f(Av)−⟨b,v⟩f(Av)-\langle b,v\ranglef(Av)−⟨b,v⟩, where AAA is a differential operator and fff is non-smooth: an obstacle, a friction term, a plasticity threshold. Splitting the variable, y=Avy=Avy=Av, separates the linear operator from the non-smooth function, and a Lagrange…

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

Shock Models and Wear Processes III: The First Passage Time of a Nondecreasing Markov Wear Process Above a Fixed Level Has an IHRA DistributionResearch Paper

Reliability theory classifies life distributions by how they age. A device whose failure rate tends to increase over time is "wearing out", and the class of distributions with increasing hazard rate average (IHRA) is the one that is closed under forming coherent systems of independent components (Birnbaum, Esary and Marshall, 1966). This makes IHRA the…

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

Shock Models and Wear Processes IV: With a Random Threshold, Shock Survival Probabilities Are Submultiplicative for Every Damage Law Iff the Threshold Is NBUResearch Paper

Reliability theory classifies life distributions by how they age. A device whose remaining life, once it has survived to age ttt, is stochastically shorter than the life of a new device is called new better than used (NBU). The NBU class, together with the classes IHR (increasing hazard rate) and IHRA (increasing hazard rate average), organizes much of the…

5 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationMarkov Chain+1·Captain: mikedeng1

Linear Programming and Markov Decision Chains 3: The Representative of a Pure Stationary Policy Is an Extreme Point of the Dual LPResearch Paper

A Markov decision chain is a controlled Markov chain: in each state the controller picks an action, collects a reward and moves to a random next state with probabilities that depend on the state and the action. Under the average reward criterion, the long-run reward per step, an optimal policy can be computed by linear programming. For chains in which every…

9 thms3 active usersReviewed
🏆Completed
Markov ChainProbabilityStochastic Systems·Captain: mikedeng1

Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model: The Discrete-Time Proximity Process Is Dual to the Branching Process with InterferenceResearch Paper

Many models in probability, statistical physics and the theory of stochastic networks are interacting particle systems: infinitely many sites, each in state 0 or 1, each updating at random according to the states of a few other sites. A basic question about such a system is ergodicity: does it have a unique stationary distribution, and does its law converge…

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

The Relation between Customer and Time Averages in Queues: H = λG on Every Sample Path When 0 < λ < ∞, G < ∞ and Each f_n Vanishes Outside [t_n, t_n + s_n] with s_n/n → 0Research Paper

Little's law L=λWL = \lambda WL=λW says that the long-run average number of customers in a system equals the arrival rate times the average time a customer spends there. It is one of the most used identities in queueing theory, and it holds on individual sample paths under weak conditions (Little 1961; Stidham 1974). Many quantities of interest are not head counts,…

11 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Globally Convergent Inexact Newton Methods I: Inexact Newton Backtracking Converges to Every Limit Point Where F′ Is Invertible, That Point Is a Zero of F, and Initial Steps Are Eventually AcceptedResearch Paper

Newton's method for a nonlinear system F(x)=0F(x) = 0F(x)=0, with F:Rn→RnF:\mathbb R^n\to\mathbb R^nF:Rn→Rn, solves the linear system F′(xk)sk=−F(xk)F'(x_k)s_k = -F(x_k)F′(xk​)sk​=−F(xk​) at every step. For large systems that solve is itself iterative (a Krylov method such as GMRES), and it is stopped early. The resulting inexact Newton methods, introduced by Dembo, Eisenstat and Steihaug (SIAM J. Numer. Anal. 19…

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

Shock Models and Wear Processes I: Under Poisson Shocks, Cumulative Nonnegative I.I.D. Damage up to a Fixed Threshold Gives an IHRA Life DistributionResearch Paper

Reliability theory classifies life distributions by how they age. The IHRA class (increasing hazard rate average) is the smallest class of life distributions that contains the exponential distributions and is closed under forming coherent systems and taking limits in distribution (Birnbaum, Esary and Marshall 1966). It is therefore the natural class for the…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach 3: Robust Optimal Values and Solution Sets over f-Divergence Balls Are ConsistentResearch Paper

Stochastic optimization asks for a decision xxx in a set X⊂Rd\mathcal X\subset\mathbb R^dX⊂Rd that minimises an expected loss EP0[ℓ(x;ξ)]E_{P_0}[\ell(x;\xi)]EP0​​[ℓ(x;ξ)] when the distribution P0P_0P0​ of the data ξ\xiξ is known only through a sample ξ1,…,ξn\xi_1,\dots,\xi_nξ1​,…,ξn​. The classical estimator, sample average approximation, replaces P0P_0P0​ by the empirical distribution P^n\widehat P_nPn​. Distributionally…

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

Deterministic Equivalents for Optimizing and Satisficing under Chance Constraints 1: Under Normality, the E-Model Chance Constraints Are Equivalent to the Convex Program (29)Research Paper

Chance-constrained programming replaces a linear program max⁡c′x\max c'xmaxc′x subject to Ax≤bAx\le bAx≤b by a problem in which some data are random and each constraint only has to hold with a prescribed probability. Charnes and Cooper introduced the idea in 1959 for scheduling heating-oil production against weather-dependent demand, and the formulation is now a standard…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

On Representatives of Subsets: Two Partitions into m Classes Have a Common System of Representatives When Any k Classes of One Meet at Least k Classes of the OtherResearch Paper

Many assignment questions reduce to one combinatorial question: given finitely many sets, can one choose a different element from each? Workers are matched to jobs they are qualified for, rows of a matrix to columns with nonzero entries. The criterion for when this is possible is Hall's marriage theorem, first stated and proved by P. Hall in a five-page…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey 2: The Optimal Preemptive Open Shop Makespan Equals the Largest Machine Load or Job LengthResearch Paper

Open shops model production and service systems in which every job must visit every machine, but the order of the visits is free: a car that needs an inspection, a wash and a tyre change, a patient who needs several tests, a student who sits several exams. The survey of Graham, Lawler, Lenstra and Rinnooy Kan (Ann. Discrete Math. 5, 1979) fixed the…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey 1: The Optimal Two-Machine Open Shop Makespan Is max{T₁, T₂, maxⱼ(aⱼ + bⱼ)}Research Paper

Shop scheduling asks how to sequence jobs that each need processing on several machines. In an open shop, a job's operations may be executed in any order, as in testing stations, repair bays, or classroom and examination timetables, where the order in which a candidate visits the stations is irrelevant. The objective studied here is the makespan Cmax⁡C_{\max}Cmax​,…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: mikedeng1

Extensions of the Queueing Relations L = λW and H = λG: Under (14) and (15) the Time Average H(t) Converges if and only if the Customer Average G(s) Does, and Then H = λGResearch Paper

Queueing results often relate an average accumulated over customers to an average accumulated over time. In the familiar relation L=λWL=\lambda WL=λW, the long-run average number in a system equals the arrival rate times the average time spent there. Glynn and Whitt study a broader relation, H=λGH=\lambda GH=λG, that can represent queue lengths and waiting times but also…

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

A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management 2: Frequent Re-solving Loses at Most O(√T) Against the Deterministic LP, Uniformly in the CapacitiesResearch Paper

Network revenue management is the problem of selling several limited, perishable resources (seats on flight legs, hotel room-nights, machine hours) to customers who arrive over time and each want a fixed bundle of them. A seller who accepts every request early may run out of the resources that the most valuable later customers need, and a seller who is too…

9 thms3 active usersReviewed
🏆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
PreviousPage 73 of 142Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5162497
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36575444
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