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

876–900 of 4812
Open1285Completed3527All4812
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Wait-and-Judge Scenario Optimization 1: For Convex Programs, Seeing s_N Support Constraints Gives P^N{V(x_N) > ε(s_N)} ≤ γ, the Value of the Variational Problem (10)Research Paper

Many decision problems in control, finance and engineering must hold against an uncertain parameter δ\deltaδ whose distribution is unknown, while samples of δ\deltaδ (measurements, historical records, simulations) are available. The scenario approach replaces the uncertain constraint by the constraints of the NNN observed samples and solves the resulting convex…

12 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability+1·Captain: mikedeng1

An Optimal Algorithm for On-line Bipartite Matching 1: RANKING Finds a Matching of Expected Size at Least n(1 − 1/e) − o(n) on Every Graph with a Perfect MatchingResearch Paper

Online matching describes allocation when requests must be answered as they arrive. A matching decision uses only the edges revealed so far and cannot be revised when later requests appear. In the bipartite setting studied by Karp, U. Vazirani, and V. Vazirani, the arriving vertices are girls and the possible partners are boys. Even when the full graph has…

10 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Supply Chain Coordination with Contracts IV: Competing Newsvendors with Proportional Allocation Have a Unique Equilibrium, and a Coordinating Buy-Back Gives the Supplier ((p(n − 1) + b)/(pn))Π(q°)Textbook

A supplier who sells through a single newsvendor retailer faces double marginalization: the retailer bears the whole cost of leftover stock but earns only the retail margin, so under a plain wholesale-price contract he orders less than the integrated supply chain would. The literature reviewed in G. P. Cachon's chapter Supply Chain Coordination with…

18 thms4 active usersReviewed
Complexity TheoryLinear OptimizationOptimization·Captain: mikedeng1

On Linear Characterizations of Combinatorial Optimization Problems II: A Small Polynomial-Time Generator of Violated Inequalities Puts the Decision Problem in PResearch Paper

Many combinatorial optimization problems ask for the largest value of a linear objective over discrete feasible solutions. A linear program over the convex hull of those solutions has the same optimum, so one approach is to describe that hull by inequalities. For matching, for example, inequalities support efficient optimization; for other problems, the…

11 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingGraph TheoryOperations Research+1·Captain: mikedeng1

Send-and-Split Method for Minimum-Concave-Cost Network Flows II: Subproblem Minimum Costs Are the Greatest Solution of the Send-and-Split Equations, Unique if Circulations Cost Positively (Theorem 2)Research Paper

Many network-design and production-planning problems ask for a cheapest way to route a commodity from supply points to demand points when the cost of an arc grows less than proportionally with the amount sent: setup charges, economies of scale, and fixed-plus-linear costs all give concave arc costs. Minimizing a concave function over the flow polytope is…

15 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Supply Chain Coordination with Contracts I: The Newsvendor Quantity-Flexibility Contract (w_q(δ), δ) Gives the Retailer at Least Π(q°) at δ = 0, the Supplier at Least Π(q°) at δ = 1Textbook

A supplier sells to a retailer who must order before a single selling season with random demand. Each firm maximizes its own expected profit, and with the simplest contract, a fixed wholesale price per unit, the retailer orders too little: he bears all the risk of unsold stock but earns only part of the margin on each sale. The supply chain as a whole then…

11 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryProbability·Captain: mikedeng1

The Chromatic Number of Random Graphs: For Fixed 0 < p < 1, Almost Every G(n,p) Has n/s₀ ≤ χ(G) ≤ (n/s₀)(1 + 3 log log n / log n), where s₀ ≈ 2 log_d n and d = 1/(1−p)Research Paper

The chromatic number χ(G)\chi(G)χ(G) of a graph is the least number of colours in a proper vertex colouring. Determining it for a typical graph was, in the words of the paper, "one of the best known and most studied unsolved problems in the theory of random graphs". For the dense random graph Gn,pG_{n,p}Gn,p​ with fixed edge probability ppp, the clique number had been known…

15 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach 2: Empirical Likelihood Intervals for the Optimal Value inf_x E[ℓ(x;ξ)] Have Exact Coverage P(χ²₁ ≤ ρ)Research Paper

Many stochastic optimization problems choose a decision by minimizing an expected loss. The optimum depends on an unknown distribution, so a data-based optimum alone gives no measure of uncertainty about the best achievable expected loss. This mission concerns a confidence set for that optimal value, rather than a confidence set for the decision itself. The…

30 thms4 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraMachine Learning+1·Captain: mikedeng1

Adaptive Subgradient Methods for Online Learning and Stochastic Optimization 2: Full-Matrix AdaGrad's Regret Is Bounded by tr(G_T^{1/2})Research Paper

Online convex optimization is the standard model for learning from a stream of data: in round ttt a learner commits to a point xtx_txt​ in a convex set X⊆Rd\mathcal X\subseteq\mathbb R^dX⊆Rd, a convex loss ftf_tft​ is revealed, and the learner pays ft(xt)+φ(xt)f_t(x_t)+\varphi(x_t)ft​(xt​)+φ(xt​), where φ\varphiφ is a fixed regularizer. Subgradient methods for this model use one fixed geometry (usually…

16 thms4 active usersReviewed
🏆Completed
Machine LearningOptimizationReinforcement Learning·Captain: mikedeng1

On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift 5: Natural Policy Gradient with Softmax Policies Is Within log|A|/(ηT) + 1/((1−γ)²T) of OptimalResearch Paper

Policy gradient methods optimize a parameterized policy directly by gradient ascent on its expected discounted return. They underlie most practical reinforcement-learning systems, yet for a long time their convergence was understood only locally: the objective θ↦Vπθ(ρ)\theta\mapsto V^{\pi_\theta}(\rho)θ↦Vπθ​(ρ) is not concave, and plain gradient ascent can stall on…

16 thms4 active usersReviewed
🏆Completed
CombinatoricsProbabilityStatistics·Captain: mikedeng1

Two Moments Suffice for Poisson Approximations: The Chen-Stein Method 2: A Dependent Bernoulli Process Is Within 2(2b₁+2b₂+b₃) of a Poisson Process in Total VariationResearch Paper

Many counting problems in probability, combinatorics and statistics ask for the law of the number of occurrences of rare, weakly dependent events: long head runs in coin tossing, matching segments between two DNA sequences, isolated vertices or small subgraphs in a random graph, clusters of points in a scan statistic. Chen's 1975 adaptation of Stein's…

8 thms4 active usersReviewed
🏆Completed
CombinatoricsProbabilityStatistics·Captain: mikedeng1

Two Moments Suffice for Poisson Approximations: The Chen-Stein Method 1: Total Variation Bound 2[(b₁+b₂)(1−e^{−λ})/λ + b₃′(1∧1.4λ^{−1/2})] for a Sum of Dependent IndicatorsResearch Paper

Counts of rare events often look Poisson even when the events are dependent. For example, a local pattern in a random graph can overlap another copy of the pattern, so the corresponding occurrence indicators are not independent. The useful question is quantitative: how far is the distribution of the total count from a Poisson distribution with the same…

8 thms4 active usersReviewed
🏆Completed
AnalysisControl TheoryDynamical Systems+1·Captain: mikedeng1

An Example on the Effect of Time Delays in Boundary Feedback Stabilization of Wave Equations: The Spectral Stability Trichotomy at the Feedback Gain k = (1 − K)/(1 + K), K = e^{−2a}Research Paper

Boundary feedback is the standard way to stabilize vibrating structures governed by wave equations: a sensor measures the velocity at the boundary and an actuator applies a force proportional to it. For the one-dimensional damped wave equation with such feedback, the closed loop is uniformly exponentially stable (Chen, 1979). In practice the measured…

16 thms4 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management 3: On a Degenerate Two-Class Instance, Frequent Re-solving Has Regret at Least Ω(√T)Research Paper

Network revenue managers sell access to limited capacity over time. An airline, for example, may have several products that use the same seat inventory, with some products earning more revenue than others. The decision to accept a request must be made when it arrives, before future requests are known. A standard way to guide that decision is to solve a…

7 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability·Captain: mikedeng1

A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management 1: Infrequent Re-solving with Thresholding Has Regret O(1), Uniformly in the Horizon T and the Capacities CResearch Paper

Network revenue management decides, in real time, which customer requests to accept when every request consumes a bundle of scarce, perishable resources: seats on several flight legs of an itinerary, room-nights of a multi-night hotel stay, bandwidth on several links. The exact dynamic program is intractable for realistic networks, so practice and theory…

11 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Assortment Optimization under Variants of the Nested Logit Model 3: With Fully-Captured Nests, the Nested-by-Revenue LP Optimum Scaled by the Factor (6) Is Feasible for the Full LPResearch Paper

Assortment optimization asks a retailer which products to offer when customers substitute among them. The nested logit model groups products into nests and is one of the most used choice models in revenue management, because it relaxes the independence of irrelevant alternatives of the plain multinomial logit model while keeping choice probabilities in…

26 thms4 active users
🏆Completed
Linear OptimizationOperations ResearchStochastic Systems·Captain: mikedeng1

Maximum Pressure Policies in Stochastic Processing Networks IV: In Reversed Leontief Networks Extreme Allocations Are Integral and Maximum Pressure Separates by ProcessorResearch Paper

Maximum pressure policies schedule a stochastic processing network by choosing, at each decision time, an allocation of processors to activities that maximizes a linear "pressure" built from the current buffer levels and the network's input-output matrix. Dai and Lin (Oper. Res. 53(2), 2005) prove that such policies are throughput optimal: they stabilize…

7 thms4 active usersReviewed
🏆Completed
Control TheoryOperations ResearchStochastic Systems·Captain: mikedeng1

Maximum Pressure Policies in Stochastic Processing Networks II: Under Assumptions 1 and 2, the Maximum Pressure Fluid Model Empties in Finite Time When the Static Planning LP Has ρ < 1Research Paper

Stochastic processing networks (Harrison 2000) model manufacturing lines, data switches, call centers and multiclass queueing networks in one framework: jobs wait in buffers, activities process jobs from one or several buffers at once, each activity may need several processors simultaneously, and routing after service may depend on the activity used. A…

10 thms4 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchStochastic Systems·Captain: mikedeng1

Stability and Instability of Fluid Models for Reentrant Lines 1: Every Work-Conserving Fluid Model of the Three-Buffer Line 1→2→1 Is Stable When m₁ + m₃ < 1 and m₂ < 1Research Paper

A reentrant line is a queueing network in which every job follows the same route and visits some stations more than once. It is the standard model of a semiconductor wafer fab, where a wafer returns to the same lithography station for each of its layers (Kumar, Re-entrant lines, Queueing Systems 13, 1993). Because jobs at different stages compete for the…

10 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity V: Projected Gradient Descent on a Convex β-Smooth Function Has Rate (3β‖x₁ − x*‖² + f(x₁) − f(x*))/tTextbook

Many optimization problems in statistics, machine learning and operations research ask to minimize a smooth convex function over a simple convex set: a box, a ball, a simplex, a cone of positive semidefinite matrices. Projected gradient descent is the most basic first-order method for such problems. It takes a gradient step and then returns to the feasible…

12 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity I: The Center of Gravity Method Satisfies f(x_t) − min f ≤ 2B(1 − 1/e)^{t/n}Textbook

Black-box convex optimization asks how many queries to an oracle are needed to minimize a convex function to accuracy ε\varepsilonε. In fixed dimension nnn the answer is of order nlog⁡(1/ε)n\log(1/\varepsilon)nlog(1/ε), and the first algorithm to attain it is the center of gravity method, discovered independently by Levin (1965) and Newman (1965). It is the opening example of cutt…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

On the Graph Structure of Convex Polyhedra in n-Space II: Whitney's Theorem, a Graph Is n-Tuply Connected iff Any Two Points Are Joined by n Disjoint PathsResearch Paper

Vertex connectivity measures how robust a network is against the failure of nodes. It can be measured in two ways that look different. One way counts the fewest nodes whose removal disconnects the network. The other counts the routes between two nodes that share no intermediate node. Whitney's theorem (1932) says that the two measures agree for every pair…

9 thms4 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchProbability+1·Captain: mikedeng1

Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms I: The Nonparametric Learn-then-Price Policy Has Regret at Most C(log n)^{1/2}/n^{1/4}Research Paper

A seller with a fixed stock of a single product and a finite selling season has to set prices without knowing how demand responds to them. This is the standard situation in revenue management: airline seats, hotel rooms, fashion goods and event tickets. The classical theory of dynamic pricing (Gallego and van Ryzin, 1994) assumes that the demand function …

15 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchProbability+1·Captain: mikedeng1

Data-Driven Robust Optimization VI: The Moment Set U^CS Has Support Function μ̂ᵀv + Γ₁‖v‖ + √(1/ε − 1)‖Cv‖, an Upper Bound on the Worst-Case Value at RiskResearch Paper

In robust optimization, a constraint is checked against every parameter value in an uncertainty set. This turns uncertainty into a deterministic optimization problem, but the set must be chosen carefully: a large set can make decisions unnecessarily conservative, while a small one can miss likely outcomes. Bertsimas, Gupta and Kallus use data to calibrate…

11 thms4 active users
🏆Completed
Convex OptimizationOperations ResearchProbability+1·Captain: mikedeng1

Data-Driven Robust Optimization IV: The Forward–Backward Deviation Set U^FB Has a Closed-Form Support Function That Bounds the Worst-Case Value at RiskResearch Paper

A robust linear constraint u⊤v≤tu^\top v \le tu⊤v≤t with uuu ranging over an uncertainty set U⊆Rd\mathcal U\subseteq\mathbb R^dU⊆Rd is tractable whenever the support function δ∗(v∣U)=sup⁡u∈Uu⊤v\delta^*(v\mid\mathcal U)=\sup_{u\in\mathcal U}u^\top vδ∗(v∣U)=supu∈U​u⊤v is. Robust optimization gains a probabilistic meaning when U\mathcal UU is chosen so that every robustly feasible decision also satisfies the…

18 thms4 active users
PreviousPage 36 of 193Next

Top contributors

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