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

2201–2225 of 4812
Open1243Completed3569All4812
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: mikedeng1

Negative Dynamic Programming I: With Non-Positive Rewards, If an Optimal Policy Exists Then an Optimal Stationary Policy ExistsResearch Paper

Many sequential decision problems accumulate costs that are never recovered: inventory holding and shortage costs, waiting times, the expected number of steps until a target is reached. Written as rewards, these are non-positive rewards summed over an infinite horizon without discounting. Ralph Strauch's paper Negative Dynamic Programming (Ann. Math.…

16 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningProbability+1·Captain: mikedeng1

Technical Note: Q-Learning: With Bounded Rewards and Learning Rates with Σα = ∞, Σα² < ∞ at Every State–Action Pair, Tabular Q-Learning Converges to Q* with Probability 1Research Paper

Q-learning is the basic model-free algorithm of reinforcement learning: an agent that does not know the transition probabilities or the reward structure of a controlled Markov process learns the optimal action values from experience alone, by a one-line update applied after every observed transition. It was introduced in C. J. C. H. Watkins' 1989 thesis,…

8 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOptimization·Captain: mikedeng1

On General Minimax Theorems 2: Kneser–Fan — If f Is Concave-Convexlike and u.s.c. in μ on Compact M, Then sup inf f = inf sup fResearch Paper

A minimax theorem asserts that for a real function f(μ,ν)f(\mu,\nu)f(μ,ν) of two variables the order of optimization does not matter:

6 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Some Theoretical Aspects of Road Traffic Research IV: Optimum Phase Times of a Two-Phase Fixed-Time Signal — When the Minimum Cycle Minimizes Average Delay, and the Optimum OtherwiseResearch Paper

A fixed-time traffic signal is set by two numbers per phase: how long the green lasts and, through the other phase's green, how long the red lasts. Traffic engineers in the early 1950s set signals by Adams' formula, the shortest cycle that can clear the arriving traffic, on the working assumption that the shortest feasible cycle also gives the least delay.…

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

On Cores and Indivisibility 1: The Housing Market's Game Without Side Payments Is BalancedResearch Paper

A market in which each trader owns one indivisible good has a basic coordination question: can all goods be reassigned so that no group of traders can withdraw its own goods and improve every member's outcome? Houses are the paper's running example. Monetary transfers and fractional houses are absent, so ordinary convex allocation arguments do not describe…

11 thms3 active users
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Some Theoretical Aspects of Road Traffic Research II: Equal Journey Times on Alternative Routes — Exactly the Routes with bᵢ < t Are Used, qᵢ = pᵢ(1 − bᵢ/t)Research Paper

Planning a road improvement requires an estimate of how traffic will redistribute over the routes affected. Because speed falls as flow rises, sending every vehicle along the route that is quickest today changes which route is quickest. J. G. Wardrop posed the question in its simplest setting in 1952: a given flow QQQ chooses among DDD alternative routes…

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

Optimal Ordering and Rationing Policies in a Nonstationary Dynamic Inventory Model with n Demand Classes I: Critical Rationing Levels z̄ₜ¹ ≥ ⋯ ≥ z̄ₜⁿ Give an Optimal Policy When Each aₜ Is 0 or 1Research Paper

A firm that holds a single stock of a product often serves customers of different priority: military and civilian requisitions, contract and spot customers, emergency and routine orders for spare parts. When stock runs short, it must decide not only how much demand to satisfy but whose. Satisfying a low-priority order now may leave the firm unable to serve…

10 thms3 active usersReviewed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

Average Optimality in Dynamic Programming with General State Space: Under (W) or (S) and Bounded Relative Discounted Values, a Limit of Discount-Optimal Policies Is Average OptimalResearch Paper

A Markov decision process with the average cost criterion asks for a policy that minimizes the long-run expected cost per unit time. The criterion is the natural one for inventory, queueing and maintenance systems that run indefinitely without a meaningful discount rate, and it is the standard benchmark in the theory of controlled Markov chains (Arapostathis…

15 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

On Finding Optimal Policies in Discrete Dynamic Programming with No Discounting 1: If G(f) ∪ H(f) Is Empty, f Maximizes the Gain and Then the Bias, and Each Improvement Step Raises (x, y, z)Research Paper

A controller observes a finite system period after period, chooses an action in each state, earns an income and moves the system at random. When future income is not discounted, the natural criterion is the average return per unit time (the gain), but many policies share the maximal gain while differing in their transient income. Blackwell (1962) showed…

16 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsMechanism Design+1·Captain: mikedeng1

On Cores and Indivisibility 2: Gale's Top Trading Cycles Give a Core Allocation Supported by Competitive PricesResearch Paper

Markets for indivisible goods, in which each participant owns one unit and wants one unit (houses, kidneys in paired donation, dormitory rooms, school seats), cannot be analysed with the convexity assumptions of classical general equilibrium theory. Shapley and Scarf (1974) introduced the housing market to ask whether the two central solution concepts of…

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

Estimating Variance From High, Low and Closing Prices I: S_t(S_t − X_t) + I_t(I_t − X_t) Has Mean σ²t for Brownian Motion With Any DriftResearch Paper

The logarithm of a share price is commonly modelled as a Brownian motion with drift, Xt=σBt+ctX_t=\sigma B_t+ctXt​=σBt​+ct. The Black–Scholes option pricing formula needs the volatility σ\sigmaσ but not the drift ccc, so a practitioner must estimate σ2\sigma^2σ2 from data. Observing the whole path would give σ2\sigma^2σ2 exactly through its quadratic variation, but a real observer sees…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOperations Research+1·Captain: mikedeng1

Duality and Stability in Extremum Problems Involving Convex Functions 3: If f Is Finite at x and g Is Finite and Continuous at Ax, Then (P) Is Stably Set and inf (P(z)) Is Continuous Near z = 0Research Paper

A convex program is useful in practice only if its optimal value responds reasonably to small changes in the data. Lagrangian and Fenchel duality theory makes this precise: the dual problem attains its optimum and has no duality gap exactly when the primal value function does not fall off infinitely steeply under small perturbations. A constraint…

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

A Dual Approach to Solving Nonlinear Programming Problems by Unconstrained Optimization 1: Approximate Minimizers of L_r(·, yᵏ) along a Bounded Maximizing Dual Sequence Are Asymptotically MinimizingResearch Paper

Constrained convex programs are routinely solved by turning them into a sequence of unconstrained problems. The classical route is the ordinary Lagrangian L0(x,y)=f0(x)+∑iyifi(x)L_0(x, y) = f_0(x) + \sum_i y_i f_i(x)L0​(x,y)=f0​(x)+∑i​yi​fi​(x), whose dual function g0g_0g0​ is in general nonsmooth and equal to −∞-\infty−∞ off the orthant y≥0y \ge 0y≥0, so maximizing it requires a constrained, nonsmooth method. In 1969…

11 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces VII: Bin Packing — P(|B_N − M| ≥ 1 + u) ≤ 8 exp(−u²/(64 N E X₁²))Textbook

Bin packing asks for the minimum number of unit-capacity bins into which a list of items with sizes in [0,1][0,1][0,1] can be packed. It is one of the basic NP-hard problems of combinatorial optimization and operations research, and its stochastic version, where the item sizes are random, has a large literature (Coffman and Lueker, Probabilistic Analysis of Packing…

6 thms3 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOperations Research+1·Captain: mikedeng1

Duality and Stability in Extremum Problems Involving Convex Functions 1: A Convex Program Is Stably Set If and Only If Its Infimum Equals the Attained Maximum of the Dual, inf (P) = max (P*)Research Paper

In convex optimization, a dual problem supplies a bound on what a primal minimization problem can achieve. The bound can be useful even when no minimizer is known, but an equality of the primal and dual values says more: it certifies that the bound is exact. In applications, one also wants a dual variable that actually attains the bound, since that variable…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryProbability·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces X: The Chromatic Number of Random Graphs — χ(G(n,p), m) Lies in an Interval of Length k with High ProbabilityTextbook

The chromatic number of the random graph G(n,p)G(n,p)G(n,p) is one of the central random variables of probabilistic combinatorics. Its order of magnitude for constant ppp, χ(G(n,p))∼n/(2log⁡1/(1−p)n)\chi(G(n,p)) \sim n/(2\log_{1/(1-p)} n)χ(G(n,p))∼n/(2log1/(1−p)​n), was settled by Bollobás ([B], 1988); the question that remains is how much χ\chiχ fluctuates around its typical value. Shamir and Spencer ([S-S], 1987) used the…

5 thms3 active usersReviewed
🏆Completed
AnalysisCombinatoricsProbability·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces V: The Convex Hull Distance — ∫ exp f_α(A,x) dP ≤ P(A)^{−α}Textbook

A product probability space (ΩN,P)(\Omega^N, P)(ΩN,P), P=μ⊗NP=\mu^{\otimes N}P=μ⊗N, concentrates its mass: a set AAA of non-negligible measure is "close" to most points. How closeness is measured decides what the statement can be used for. The Hamming distance (Chapter 2 of the paper) counts coordinates in which a point differs from AAA; it gives Gaussian concentration, but only for…

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

Some Aspects of the Sequential Design of Experiments I: Greedy Sampling with Density-Zero Forced Draws Earns max(α, β) per Draw from Any Two Populations with Finite MeansResearch Paper

An experimenter can draw observations from two populations AAA and BBB, one at a time, and wants the sum of the observations to be as large as possible. The populations might be two treatments, two seed varieties or two manufacturing processes; their means are unknown. Each draw both earns a reward and tells the experimenter something about the population it…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research+1·Captain: mikedeng1

Inventory Control in a Fluctuating Demand Environment I: With Linear Order Costs, a World-Dependent Basestock Policy Is Optimal over the Infinite HorizonResearch Paper

An inventory controller must decide how much to order while demand changes with an observed external condition. A single demand rate misses that dependence: the same inventory position can justify different orders when the condition changes. Song and Zipkin's 1993 study asks whether a simple policy remains optimal when the condition follows a…

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

Regenerative Stochastic Processes 1: The State Probabilities of an Aperiodic Equilibrium Process Converge to (1/μ₁)∫φ_A(v){1 − F(v)}dvResearch Paper

Many stochastic systems studied in operations research "start afresh" at certain random instants: a single-server queue each time a customer arrives to find the server idle, an inventory system each time stock is replenished to its order level, a reliability system each time a failed unit is replaced. Between such instants the system may evolve in a…

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

Regenerative Stochastic Processes 3: A Cumulative Process Has Mean (κ₁/μ₁)t + o(t) and Variance (t/μ₁){σ₂² − 2ρσ₁σ₂κ₁/μ₁ + σ₁²(κ₁/μ₁)²} + o(t)Research Paper

Many stochastic systems accumulate a real-valued quantity while repeatedly returning to a state at which a new cycle begins. A queue may accumulate work or cost, a component may accumulate wear, and a recurrent system may accumulate time in a state. The observations at a fixed clock time usually cut through a cycle. This makes the moments of the observed…

7 thms3 active usersReviewed
🏆Completed
Complexity TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming 1: The Predictor–Corrector Algorithm Between N₂(1/4) and N₂(1/2) Attains Precision t in O(√n·t) IterationsResearch Paper

Linear programming asks for the best value of a linear objective subject to linear equations and inequalities. Primal-dual interior-point methods seek feasible primal and dual solutions while keeping every constrained coordinate positive. The resulting pair has a measurable gap between its objective values, so an algorithm can stop when the gap is below a…

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

Random Walks in a Random Environment 1: Transience to +∞, to −∞, or Recurrence According to Σ n⁻¹P(ρ_n > 1) < ∞, Σ n⁻¹P(ρ_n < 1) < ∞, or Both Infinite (E ln σ < 0, > 0, = 0)Research Paper

A random walk on the integers in which the probability of stepping right depends on the current site is the simplest model of motion through a disordered medium: a particle diffusing in a crystal with impurities, a molecule moving along a heterogeneous polymer, or a gene frequency drifting under fluctuating selection. When the site-dependent probabilities…

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

Optimal Pricing and Return Policies for Perishable Commodities I: Unlimited Returns at Partial Credit Coordinate the Channel for Every Demand DistributionResearch Paper

A manufacturer of a perishable good (newspapers, magazines, bread, seasonal fashion, printed books) sells through a retailer who must commit to an order before demand is known. Unsold units lose most of their value; unmet demand costs goodwill. When the retailer alone bears the risk of leftovers, it orders less than an integrated firm would, and the channel…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsNumber TheoryProbability+1·Captain: mikedeng1

A New Class of Random Number Generators 1: For Prime m = bʳ + bˢ − 1, Every Nontrivial Add-with-Carry Sequence Is Periodic After r Steps, with Period the Order of b mod mResearch Paper

Simulation, Monte Carlo integration and randomized algorithms consume long streams of numbers that should behave like independent uniform draws. A deterministic generator with finite state is eventually periodic, so its period is the first figure of merit: a stream cannot be longer than its cycle. G. Marsaglia and A. Zaman, A new class of random number…

17 thms3 active usersReviewed
PreviousPage 89 of 193Next

Top contributors

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