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.

3542 completed missions

Missions

2051–2075 of 3542
Open1270Completed3542All4812
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Toward Robust Revenue Management: Competitive Analysis of Online Booking I: The Nested Two-Fare Protection Level Is Optimally b(r)-CompetitiveResearch Paper

Revenue management decides how much of a fixed, perishable capacity (airline seats, hotel rooms) to sell at each price. The classical single-leg models, starting with Littlewood's two-fare rule (1972) and continued by Belobaba, Brumelle–McGill and Lee–Hersh, assume that demand for each fare class follows a known probability distribution and maximise…

8 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryDynamic ProgrammingOperations Research+1·Captain: mikedeng1

Bellman's Dynamic Programming VIII: Multi-Stage Games, Games of Survival and the Extended Min-Max TheoremTextbook

Chapter X of Richard Bellman's Dynamic Programming (Princeton University Press, 1957; Princeton Landmarks edition 2010, DOI 10.2307/j.ctv1nxcw0f) carries the functional-equation method of the earlier chapters from one-player decision processes to two-player zero-sum games that are played over many stages. At each stage the two players make simultaneous…

9 thms3 active usersReviewed
🏆Completed
Calculus of VariationsControl TheoryDynamic Programming+3·Captain: mikedeng1

Bellman's Dynamic Programming VII: Convergence of Discrete Approximations in the Calculus of VariationsTextbook

Chapter IX of Richard Bellman's Dynamic Programming (Princeton University Press, 1957; Princeton Landmarks edition 2010, DOI 10.2307/j.ctv1nxcw0f) recasts problems of the calculus of variations with constraints as dynamic programming processes. A variational problem with an inequality constraint on the control, such as 0≤y≤x0 \le y \le x0≤y≤x, is awkward for the…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research+1·Captain: mikedeng1

Linear Programming: Foundations and Extensions VI: The Homogeneous Self-Dual Predictor–Corrector MethodTextbook

Interior-point methods are the standard polynomial-time algorithms for linear programming, and the path-following method that practitioners implement (Chapter 18 of Vanderbei's Linear Programming: Foundations and Extensions) comes without a complete convergence proof. Chapter 22 of the same book presents a closely related algorithm for which a complete…

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

Minimization Methods for Non-Differentiable Functions IV: Linear Convergence of the Subgradient Method under Level-Set Shape ConditionsTextbook

The subgradient method minimizes a convex function fff on Rn\mathbb{R}^nRn that need not be differentiable, by stepping against an arbitrary subgradient. With stepsizes hk→0h_k \to 0hk​→0, ∑hk=∞\sum h_k = \infty∑hk​=∞ it converges (Shor, Theorem 2.2), but in general only slowly: no stepsize rule that ignores the structure of fff gives a geometric rate. Section 2.3 of N. Z. Shor's Minim…

9 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability+1·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems VI: The (SEN) Assumptions and the Average Cost Optimality InequalityTextbook

Queueing control problems (admission control, routing, service-rate selection, flow control) are naturally posed as Markov decision chains with a denumerably infinite state space, such as the number of customers in a buffer, and are usually judged by their long-run average cost per unit time. When the state space is finite, Chapter 6 of Sennott's book shows…

12 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Makespan Minimization in Job Shops: A Linear Time Approximation Scheme: The Interval LP Is Feasible at the Restricted OptimumResearch Paper

The job shop scheduling problem asks for a nonpreemptive schedule of jobs on machines, each job a fixed sequence of operations with prescribed machines and processing times, that minimizes the time at which the last operation completes. It is one of the most studied hard problems of combinatorial optimization: even very constrained versions are strongly…

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

Analysis and Algorithms for Service Parts Supply Chains VII: Palm's Theorem for Nonstationary DemandTextbook

Spare-parts inventory models for repairable items rest on Palm's theorem: if demands arrive as a Poisson process with constant rate λ\lambdaλ and each demanded unit spends an independent, identically distributed resupply time with mean τˉ\bar\tauτˉ in the pipeline, the number of units in resupply is Poisson with mean λτˉ\lambda\bar\tauλτˉ in steady state. Stock levels,…

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

Elements of Queueing Theory V: Strassen's Theorems and the Stochastic Ordering of QueuesTextbook

Chapters 1–3 of Baccelli and Brémaud's Elements of Queueing Theory compute exact quantities: Palm identities, stability criteria, PASTA, Pollaczek–Khinchin. Chapter 4 asks a different question. When you cannot compute a queue, can you at least say it is better than another one?

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

Elements of Queueing Theory III: Stationary Regimes of Stochastic RecurrencesTextbook

Chapter 2 of Baccelli and Brémaud's Elements of Queueing Theory asks when a queue has a stationary regime. §§2.1–2.4 answer it for the single-server and multiserver queues by Loynes' monotone construction. §§2.5 and 2.11 answer it for the general object those constructions are instances of: a stochastic recurrence

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

Elements of Queueing Theory II: The Loynes Stability Theorem and CouplingTextbook

Chapter 1 of Baccelli and Brémaud's Elements of Queueing Theory builds a calculus for stationary queues. Chapter 2 asks the prior question: when is there a stationary queue at all?

13 thms3 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research+1·Captain: mikedeng1

Linear Programming: Foundations and Extensions IV: Existence of the Central PathTextbook

Interior-point methods solve linear programs by moving through the interior of the feasible region instead of along its edges, as the simplex method does. The methods used in practice are path-following methods: they track a curve, the central path, that runs through the interior of the feasible region and ends at an optimal solution. Before any such method…

5 thms3 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research+1·Captain: mikedeng1

Linear Programming: Foundations and Extensions II: Farkas' Lemma and Strict Complementary SlacknessTextbook

Every linear program comes with a second linear program, its dual, and most of what is known about linear programming is a statement about how the two interact. Weak duality gives certificates of optimality; strong duality says those certificates always exist; complementary slackness turns optimality into a system of equations. These three facts are the…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research+1·Captain: mikedeng1

Minimization Methods for Non-Differentiable Functions XI: Convexity and Subgradients of the Value Function in Decomposition with Respect to VariablesTextbook

Large convex programs often have a block structure: a small set of "complicating" variables xxx couples otherwise separate subproblems in the remaining variables yyy. Decomposition with respect to variables fixes xxx, solves the subproblem in yyy, and treats the optimal subproblem value as a function of xxx alone. The outer problem in xxx is then small but nonsmooth,…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOperations Research+1·Captain: mikedeng1

Minimization Methods for Non-Differentiable Functions X: The Space-Dilation Ellipsoid Method Localizes the Solution in Ellipsoids Shrinking by the Ratio q_nTextbook

The ellipsoid method is the algorithm that settled the polynomial-time solvability of linear programming (Khachiyan, 1979) and that underlies the equivalence of separation and optimization in combinatorial optimization (Grötschel, Lovász and Schrijver, 1981). Its origin is in nonsmooth convex optimization. In 1976 Yudin and Nemirovskii proposed a modified…

8 thms3 active usersReviewed
🏆Completed
AnalysisConvex OptimizationOptimization·Captain: mikedeng1

Minimization Methods for Non-Differentiable Functions II: Convex Functions Are Almost Differentiable and Their Almost-Gradients Are SubgradientsTextbook

Gradient methods assume a continuous gradient; subgradient methods assume convexity. Many objective functions met in practice satisfy neither. Shor's example is economic planning, where components of the objective are piecewise-smooth, not necessarily convex functions of a parameter describing the productivity of a unit, and where minimax formulations…

9 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems XIII: Lyapunov Criteria and z Standard Markov Chains with CostsTextbook

Average cost control of queues rests on a small amount of Markov chain theory: when does a chain with costs have a well defined long-run average cost, and how can that be checked for a concrete model with an unbounded state space? Appendix C of L. I. Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999, doi:10.1002/9780470…

12 thms3 active usersReviewed
🏆Completed
AnalysisProbability·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems XII: A Tauberian Theorem Linking Abel and Cesàro Means of Nonnegative SeriesTextbook

In the theory of Markov decision chains two cost criteria dominate: the discounted cost, in which a cost incurred at time nnn is weighted by αn\alpha^nαn for a discount factor α∈(0,1)\alpha \in (0,1)α∈(0,1), and the average cost, the long-run cost per unit time. A standard route to average cost optimal policies is to solve the discounted problem and let α→1−\alpha \to 1^-α→1−. That…

14 thms3 active usersReviewed
🏆Completed
AnalysisProbability·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems XI: The Generalized Dominated Convergence Theorem for Approximating DistributionsTextbook

Linn Sennott's Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999) studies Markov decision chains with countably many states, finite action sets and unbounded nonnegative costs. Its main computational device, the approximating sequence method (Definition 2.5.1, p. 28), replaces the countable state space SSS by an increasing…

12 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability+1·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems X: Average Cost Optimization of Continuous Time Markov Decision ChainsTextbook

Many queueing systems evolve in continuous time: customers arrive according to a Poisson process, services take exponentially distributed times, and a controller may change the service rate, admit or reject customers, or route them whenever the state changes. Minimizing the long-run average cost of such a system is a standard problem in the control of…

11 thms3 active users
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems IX: Bounded Mean Residual Lifetimes Imply Finite Moments of All OrdersTextbook

In a discrete-time queue the service of a customer lasts a random number YYY of slots. When such a system is modelled as a Markov decision chain (Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems, Wiley, 1999, DOI 10.1002/9780470317037, Chapter 9), the state must record how much service is still owed, and the controller only observes…

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

Stochastic Dynamic Programming and the Control of Queueing Systems VIII: Computing Average Cost Optimal Policies by Approximating SequencesTextbook

Control problems for queueing systems (admission control, service rate control, routing to parallel servers) are naturally modelled as Markov decision chains whose state is a vector of queue lengths. The state space is therefore denumerably infinite, and the performance measure of interest is usually the long-run average cost per slot. For such models the…

14 thms3 active users
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research+1·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems IV: Average Cost Optimal Stationary Policies Exist for Finite State SpacesTextbook

Controlled queues, inventories and communication links are run for a long time, and the quantity an operator usually cares about is the long-run average cost per period rather than a discounted total. The average cost criterion is harder to work with than the discounted one: its value is a lim sup⁡\limsuplimsup of Cesàro means, it is not given by a contraction, and for…

15 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability+1·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems II: The Discount Optimality EquationTextbook

Control problems for queueing systems (admission control, routing, service rate selection, inventory replenishment) are naturally modelled as Markov decision chains with a countable state space, such as the number of customers in a buffer, and with costs that grow without bound in the state, such as holding costs proportional to queue length. The expected…

12 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability+1·Captain: mikedeng1

Stochastic Dynamic Programming and the Control of Queueing Systems I: Finite Horizon Optimality and Approximating SequencesTextbook

Controlled queueing systems (admission control, routing, service-rate selection) are naturally modelled as Markov decision chains whose state is a buffer content and therefore ranges over a countably infinite set. Linn Sennott's Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999, DOI 10.1002/9780470317037) develops the dynamic…

14 thms3 active usersReviewed
PreviousPage 83 of 142Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5197499
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36595448
5NINickrobbins953288156
6VEvebis25800
7FIfizzyinc321715
8SHshivm17500
9SCShuze Chen9455324
10KMkmehltretter82925261

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