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

251–275 of 3527
Open1285Completed3527All4812
🏆Completed
Algorithmic Game TheoryOptimizationTopology·Captain: mikedeng1

On General Minimax Theorems 1: For a Minimal Finite Y with Every f(·, y) Quasi-Concave and u.s.c. on Convex M, One μ₀ ∈ M Has f(μ₀, y) < c for All y ∈ YResearch Paper

A minimax theorem asserts that, for a function f(μ,ν)f(\mu, \nu)f(μ,ν) of two variables,

11 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Revenue Management Under a General Discrete Choice Model of Consumer Behavior 1: The Optimal Policy Offers Only Nondominated Sets, a Larger One the More Capacity and the Less Time RemainResearch Paper

A seller with one limited inventory pool can choose which fare products to show in each selling period. When customers choose among the displayed products, showing another fare can both add sales and divert buyers from a more expensive fare. A fixed ranking of fares therefore does not by itself tell the seller which products to offer. Talluri and van…

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

Optimal Pricing and Return Policies for Perishable Commodities II: Neither Unlimited Returns at Full Credit nor a No-Returns Policy Coordinates the ChannelResearch Paper

Manufacturers of perishable goods must decide how much inventory risk to leave with retailers. A retailer who pays for every ordered unit may order less than is best for the manufacturer and retailer together; a generous return policy changes that incentive. Pasternack studies this question in a single-period setting, with a fixed selling price, uncertain…

9 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationMarkov Chain+1·Captain: mikedeng1

Linear Programming and Sequential Decisions: An Optimal Solution of the Equilibrium LP Yields a Stationary Decision Rule of Least Expected Monthly CostResearch Paper

Alan S. Manne's Linear Programming and Sequential Decisions (Management Science 6(3), 1960, pp. 259–267) is the first formulation of an infinite-horizon, average-cost sequential decision problem as a linear program. The illustration is a single-item inventory problem, but the construction, with unknowns indexed by a state and a decision and constraints…

13 thms5 active usersReviewed
🏆Completed
AnalysisOperations ResearchProbability·Captain: mikedeng1

The Data-Driven Newsvendor Problem: New Bounds and Insights II: Every Log-Concave Demand Has Weighted Mean Spread at Least min(b,h)/(b+h)Research Paper

The newsvendor problem is the basic single-period inventory model: a decision maker orders qqq units before a random demand DDD is observed, pays b>0b>0b>0 per unit of unmet demand and h>0h>0h>0 per unit left over, and minimizes the expected cost C(q)=E[b(D−q)++h(q−D)+]C(q)=E[b(D-q)^+ + h(q-D)^+]C(q)=E[b(D−q)++h(q−D)+]. When the distribution of DDD is known, the optimal order is the b/(b+h)b/(b+h)b/(b+h) quantile of DDD. In practice…

9 thms5 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Loss Networks 1: The Primal Problem Has a Unique Optimum x_r = ν_r ∏_j (1 − B_j)^{A_jr}; the Conditions on B Are Solvable, Uniquely if rank A = J, and Biject with Dual OptimaResearch Paper

A loss network carries calls that require capacity on one or more links. A call is accepted only when every required link has enough free circuits; otherwise it is lost. This makes the traffic on different links dependent even when calls on different routes arrive independently. Network operators need to know where capacity constraints bind and how offered…

11 thms5 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

On Tail Probabilities for Martingales 1: If X_n ≤ 1 and E{X_n | ℱ_{n−1}} ≤ 0, Then P{S_n ≥ a and T_n ≤ b for Some n} ≤ (b/(a+b))^{a+b} e^a ≤ exp[−a²/2(a+b)]Research Paper

For sums of independent bounded random variables, the inequalities of Bernstein and Bennett bound the probability of a large deviation by an exponential in the deviation and the variance (Bennett 1962; Hoeffding 1963). Many processes met in probability, statistics and learning theory are not sums of independent terms but martingales or supermartingales:…

19 thms5 active users
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

A Linear Programming Approach to the Cutting Stock Problem—Part II 2: For a Linear-Fractional Objective, a Basic Feasible Solution with No Improving Edge Is a Global MinimumResearch Paper

In the cutting stock problem, stock rolls of length LLL are cut into pieces of lengths l1,…,lml_1,\dots,l_ml1​,…,lm​ to fill orders. Part I of Gilmore and Gomory's work (Opns. Res. 9 (1961)) solved its linear programming relaxation by the simplex method with column generation: the columns (cutting patterns) are too many to list, so each simplex iteration finds an improving…

8 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

A Linear Programming Approach to the Cutting-Stock Problem: If No Slack and No Knapsack Pattern Prices Out, the Current Basic Solution Is a Minimum of the Cutting-Stock LPResearch Paper

A cutting-stock shop receives orders for pieces of several lengths and cuts them from a limited menu of longer stock lengths. Each stock length has a cost. The shop can repeat any cutting pattern, so the central optimization question is which patterns meet the demand at least cost. The direct linear program has a variable for every possible pattern. Even a…

13 thms5 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

The Intersection Graphs of Subtrees in Trees Are Exactly the Chordal Graphs: A Finite Graph Is a Subtree Graph If and Only If It Is ChordalResearch Paper

Chordal graphs (graphs in which every long cycle has a shortcut edge) appear wherever a sparse symmetric structure has to be eliminated without creating new interactions: Gaussian elimination on sparse symmetric matrices (Rose 1970), acyclic database schemes, junction trees for probabilistic graphical models, and phylogenetic and scheduling problems. In all…

11 thms5 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization+1·Captain: mikedeng1

Matching, Euler Tours and the Chinese Postman I: The Convex Hull of Nonnegative Integer Parity Solutions Is the Polyhedron of Odd-Set InequalitiesResearch Paper

The Chinese postman problem, posed by Meigu Guan (Kwan Mei-Ko) in 1962, asks for a shortest closed walk in a graph that traverses every edge at least once: the route of a postman who must cover every street and return to the post office. It is the basic model of arc routing (street sweeping, snow ploughing, meter reading, inspection of networks), and it is…

11 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: mikedeng1

MNL-Bandit: A Dynamic Learning Approach to Assortment Selection I: The Epoch-Based UCB Policy Has Regret at Most C₁√(NT log NT) + C₂N log² NT Under the No-Purchase AssumptionResearch Paper

A retailer that decides which products to display, an online platform that decides which items to show in a recommendation slot, and an airline that decides which fare classes to open all face the same problem: the set of options offered changes what customers buy, and the substitution pattern is not known in advance. The multinomial logit (MNL) model is…

15 thms5 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchStochastic Systems·Captain: mikedeng1

Stability and Instability of Fluid Models for Reentrant Lines 4: The Lu–Kumar Network Has an Unstable Work-Conserving Fluid Model iff m₂ + m₄ ≥ 1Research Paper

A reentrant line is a queueing network in which every customer follows one fixed route but may return to a station after visiting another one. A manufacturing line can have this pattern when a product revisits the same machine at different processing stages. A station can then have little nominal workload and still face unstable queues under an unfortunate…

14 thms5 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchStochastic Systems·Captain: mikedeng1

Stability and Instability of Fluid Models for Reentrant Lines 5: Without Immediate Feedback, Every Work-Conserving Fluid Model of a Two-Station Kelly-Type Line Is StableResearch Paper

A multiclass queueing network can be unstable even when every station has enough capacity on average: the queue lengths grow without bound although each server's nominal load is below one. Kumar and Seidman, Lu and Kumar (1991) and Rybko and Stolyar (1992) exhibited such networks under simple priority disciplines. This raised the question of which networks…

11 thms5 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability+1·Captain: mikedeng1

Online Stochastic Matching: Beating 1-1/e 1: When OPT = Ω(n), the Two Suggested Matchings Algorithm Achieves ALG/OPT ≥ (1 − 2/e²)/(4/3 − 2/(3e)) − ε ≈ 0.670 with Probability 1 − e^(−Ω(n))Research Paper

Online bipartite matching models a platform that must commit each arriving request to a resource immediately. The motivating application of Feldman, Mehta, Mirrokni and Muthukrishnan is display advertising: an ad server knows from past traffic how many impressions of each type (web page, audience segment) to expect, sells them to advertisers in advance, and…

28 thms5 active users
🏆Completed
Dynamic ProgrammingLinear OptimizationOperations Research+1·Captain: mikedeng1

A Probabilistic Production and Inventory Problem: The Optimal Discounted Cost Is the Greatest Point of the Constraint Set (9) and the Unique Optimum of the Linear Program (P2)Research Paper

A Markov decision process with finitely many states and actions and a discounted cost criterion can be solved in three classical ways: policy iteration, value iteration, and linear programming. The third goes back to F. d'Epenoux's paper A Probabilistic Production and Inventory Problem (Management Science 10(1), 1963, partly redrafted from a translation of…

10 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: mikedeng1

Coordinating Inventory Control and Pricing Strategies with Random Demand and Fixed Ordering Cost: The Finite Horizon Case 1: Additive Demand: k-Concave Profit-to-Go, Optimal (s, S, p) PolicyResearch Paper

A retailer that sets both its replenishment quantities and its prices over a finite selling season faces a coupled decision: the price shapes the demand that the inventory must serve, and the inventory position shapes which price is worth charging. With a fixed cost per order, the classical inventory answer is the (s, S) policy of Scarf (1960): when the…

11 thms5 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization+1·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity XV: SVRG with η = 1/(10β) and k = 20κ Contracts the Expected Optimality Gap by 0.9 per EpochTextbook

Many optimization problems in machine learning minimize an average of losses, one loss for each observation. A full gradient step examines every observation, while a stochastic gradient step examines one. The latter is cheaper per step, but its sampled gradient can remain noisy even near the optimum. Section 6.3 of Bubeck's monograph studies stochastic…

14 thms5 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity III: Projected Subgradient Descent with η = R/(L√t) Satisfies f(average) − f(x*) ≤ RL/√tTextbook

Many convex optimization problems in machine learning and statistics have objectives that are convex but not differentiable: hinge losses, ℓ1\ell_1ℓ1​ penalties, maxima of finitely many affine functions, and the dual functions of Lagrangian relaxations. Methods that rely on gradients do not apply to them directly, while cutting-plane methods such as the…

15 thms5 active users
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity II: For t ≥ 2n² log(R/r) the Ellipsoid Method Satisfies f(x_t) − min f ≤ (2BR/r)·exp(−t/(2n²))Textbook

The ellipsoid method is the cutting-plane algorithm that settled the polynomial-time solvability of linear programming and, more generally, of convex optimization over any set that comes with an efficient separation oracle. It was introduced for convex minimization by Shor and by Yudin and Nemirovski in the 1970s, and Khachiyan used it in 1979 to give the…

11 thms5 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Rademacher and Gaussian Complexities: Risk Bounds and Structural Results 3: Monotone, Absolutely Homogeneous, Convex-Hull Invariant and Subadditive R_n, and the 2L Bound for L-Lipschitz Maps Fixing 0Research Paper

Generalization bounds in statistical learning theory control the gap between the empirical and the true performance of a predictor chosen from a class FFF. Bartlett and Mendelson (JMLR 3, 2002) showed that this gap is governed by the Rademacher complexity of a loss class built from FFF, and that, unlike the VC dimension, this complexity can be estimated from…

7 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

Asymptotic Optimality of Order-up-to Policies in Lost Sales Inventory Systems: Ordering Up to the Newsvendor Level for Penalty b + τh Is Asymptotically Optimal as b → ∞Research Paper

Periodic-review inventory systems face a simple choice each period: how much to order before the next demand is known. When unmet demand is lost, the order can affect the stock available several periods later without preserving a backlog that records earlier shortages. This makes the optimal policy difficult to describe when replenishment takes time. An orde…

16 thms5 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Rademacher and Gaussian Complexities: Risk Bounds and Structural Results 1: With Probability 1 − δ, Expected Loss ≤ Empirical Dominating Cost + R_n(φ̃∘F) + √(8 ln(2/δ)/n) for Every f in FResearch Paper

A learning algorithm picks a predictor fff from a class FFF after looking at nnn training examples, and the quantity of interest is its expected loss on a fresh example. Since fff depends on the data, its training error is a biased estimate of that loss, and a risk bound quantifies the bias uniformly over the class: with high probability, every f∈Ff \in Ff∈F has expected…

10 thms5 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: mikedeng1

Reversibility and Stochastic Networks II: Migration Processes with Blocking — Reversibility and Product-Form EquilibriumTextbook

A migration process is a continuous-time Markov model of a population spread over JJJ sites, called colonies, in which individuals move one at a time: between colonies, out of the system, or into it from outside. The model was introduced by Whittle (1967) and Kingman (1969) and is the framework of Chapter 2 of F. P. Kelly, Reversibility and Stochastic Networks…

10 thms5 active usersReviewed
🏆Completed
Discrete GeometryLinear OptimizationOperations Research+1·Captain: mikedeng1

Sensitivity Theorems in Integer Linear Programming: Every Integral m×n Matrix Has Chvátal Rank at Most 2^(n³+1)·n^(5n)·Δ(A)^(n+1)Research Paper

An integer linear program max⁡{wx:Ax≤b, x integral}\max\{wx : Ax \le b,\ x \text{ integral}\}max{wx:Ax≤b, x integral} is usually attacked through its linear programming relaxation max⁡{wx:Ax≤b}\max\{wx : Ax \le b\}max{wx:Ax≤b}, which drops the integrality constraint. Two questions follow at once. How far can an optimal solution of the relaxation be from an optimal integer solution? And how many rounds of rounding-based cutting…

12 thms5 active usersReviewed
PreviousPage 11 of 142Next

Top contributors

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