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

701–725 of 3527
Open1285Completed3527All4812
🏆Completed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

Matching, Euler Tours and the Chinese Postman IV: Every Connected, Even, Symmetric Mixed Graph Has an Euler TourResearch Paper

A postman, a snowplough or a street sweeper must traverse every street of a district and return to the depot. When some streets are one-way, the street network is a mixed graph: some edges are directed and must be traversed in a prescribed direction, the others are undirected and may be traversed either way. The first question about such a route is whether…

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

Paths, Trees, and Flowers I: Matching-Duality Theorem — the Maximum Cardinality of a Matching Equals the Minimum Capacity-Sum of an Odd-Set CoverResearch Paper

A matching in a graph is a set of edges no two of which share a vertex. Finding a matching of maximum cardinality is one of the basic problems of combinatorial optimization: it models pairing tasks (workers to shifts, kidney donors to recipients, players to rounds), it is a subroutine of algorithms for the travelling salesman and Chinese postman problems,…

16 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows: With No Negative Marginal Cost Column, the Set Covering LP Is Optimal and Bounds the VRPTW Optimum from BelowResearch Paper

The vehicle routing problem with time windows (VRPTW) asks for minimum-cost routes from a central depot that serve every customer exactly once, respecting vehicle capacity and a time interval in which each customer's service must begin. It models school bus routing, parcel and retail distribution, and dial-a-ride services. Desrochers, Desrosiers and Solomon…

13 thms4 active usersReviewed
🏆Completed
Information TheoryOptimizationProbability+1·Captain: mikedeng1

I-Divergence Geometry of Probability Distributions and Minimization Problems 1: Cyclic I-Projections onto Linear Sets of a Finite Space Converge to the I-Projection onto Their IntersectionResearch Paper

Fitting a probability distribution to prescribed margins or moments is a basic task in statistics and information theory. Starting from a reference distribution, one can enforce one constraint at a time by choosing the closest distribution in I-divergence, then cycle through the constraints. In a contingency table this procedure is iterative proportional…

14 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Scheduling of Vehicles from a Central Depot to a Number of Delivery Points: The Savings Procedure Always Ends in a Feasible Truck Allocation Whose Mileage Is the Initial Less the Linked SavingsResearch Paper

Delivering goods from one depot to many customers with a fleet of trucks is the vehicle routing problem. Dantzig and Ramser formulated it in 1959 as the "truck dispatching problem" (Management Sci. 6 (1959), doi:10.1287/mnsc.6.1.80). Five years later Clarke and Wright proposed the savings procedure (Oper. Res. 12 (1964), 568–581, doi:10.1287/opre.12.4.568):…

12 thms4 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions: PMD Attains f(xⁿ) − f(u) ≤ σₙ⁻¹D_ψ(u, x⁰) and Its Iterates Converge to a MinimizerResearch Paper

Convex minimization often has a simple objective but no useful closed form for its minimizer. A proximal method replaces one difficult minimization by a sequence of regularized minimizations. The familiar quadratic regularizer treats all directions through a Euclidean norm. In applications with nonnegative variables, entropy-like geometry can be more…

9 thms4 active usersReviewed
🏆Completed
Complexity TheoryDynamic ProgrammingOperations Research+1·Captain: mikedeng1

The Complexity of Markov Decision Processes I: A Boolean Circuit Is True Iff Its Finite-Horizon Markov Decision Process Has Optimal Expected Cost ZeroResearch Paper

Markov decision processes are the standard model of sequential decision making under uncertainty in operations research, control and artificial intelligence. Their finite-horizon, discounted and average-cost versions are all solvable in polynomial time, by dynamic programming or linear programming. Papadimitriou and Tsitsiklis (The Complexity of Markov…

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

The Complexity of Markov Decision Processes III: The Optimal Discounted Cost of a Deterministic Process Is the Least Discounted Cost of a SigmaResearch Paper

A Markov decision process with finitely many states and decisions, a discount factor β∈(0,1)\beta\in(0,1)β∈(0,1) and the objective of minimizing expected discounted cost is the basic model of sequential decision making in operations research and reinforcement learning. It is solvable in polynomial time by linear programming. Papadimitriou and Tsitsiklis (Math. Oper. Res.…

7 thms4 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Poisson Approximation for Dependent Trials 1: For φ-Mixing Bernoulli Trials, |Eh(W) − 𝒫_λh| ≤ 6 min(λ^{−1/2}, 1)[Var W − λ + 2(2m+1)Σp_i² + 4(λ+1)nφ(m+1)]Research Paper

A sum of many rare events is approximately Poisson. For independent Bernoulli trials this is the classical law of small numbers, and its quantitative form goes back to Prohorov (1953) and Le Cam (1960): if X1,…,XnX_1,\dots,X_nX1​,…,Xn​ are independent with P(Xi=1)=piP(X_i=1)=p_iP(Xi​=1)=pi​, then the law of W=∑iXiW=\sum_i X_iW=∑i​Xi​ is close to the Poisson law with mean λ=∑ipi\lambda=\sum_i p_iλ=∑i​pi​, with an error…

19 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Assortment Optimization under Variants of the Nested Logit Model 6: For δ > 1, the Powers-of-δ LP Optimum Scaled by (δ^(2γ̄+1), δ^(γ̄+1)) Is Feasible for the Full LPResearch Paper

Assortment optimization asks which products a retailer should offer when customers choose among the offered products according to a probabilistic choice model, so as to maximize expected revenue. Under the nested logit model the products are grouped into nests: a customer first picks a nest, then a product inside it. The model is the standard relaxation of…

21 thms4 active users
🏆Completed
Linear OptimizationProbabilityStatistics·Captain: mikedeng1

Optimal Estimation of Executive Compensation by Linear Programming II: LP Estimates Are Consistent When the True Optimum Is Unique and NondegenerateResearch Paper

In 1955 Charnes, Cooper and Ferguson proposed to estimate the weights of an executive compensation scheme by linear programming instead of least squares: the weights minimise a sum of absolute deviations subject to ranking, ceiling and floor constraints, which is a linear program. The coefficients of that program are not known exactly. They are averages of…

7 thms4 active usersReviewed
🏆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
🏆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
PreviousPage 29 of 142Next

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