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

2151–2175 of 4812
Open1265Completed3547All4812
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: mikedeng1

Contact Interactions on a Lattice II: If λₖ/μ < k/(2d − 1), the Expected Size of a Contact Process Is Integrable in TimeResearch Paper

The contact process is the basic model of an infection spreading on a graph: infected sites recover at a constant rate, and healthy sites are infected at a rate that depends on how many of their neighbours are infected. T. E. Harris introduced it in Contact Interactions on a Lattice (Ann. Probab. 2, 1974, doi:10.1214/aop/1176996493), and it became one of…

13 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Global Convergence Properties of Conjugate Gradient Methods for Optimization II: Conjugate Gradient Methods with β_k ≥ 0 and Property (*) Are Globally Convergent under Sufficient DescentResearch Paper

Nonlinear conjugate gradient methods minimize a smooth function fff of nnn variables using only function values, gradients and a few vectors of storage. They are the standard choice when nnn is too large for quasi-Newton matrices, and they remain building blocks of large-scale solvers in optimization, scientific computing and machine learning. The method of Polak…

5 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints 2: Near the Optimal Ratio, a Maximum-Weight Initial Set Is ρ-MaximalResearch Paper

The single-machine sequencing problem with precedence constraints, written 1∣prec∣∑wjCj1\mid\mathrm{prec}\mid\sum w_jC_j1∣prec∣∑wj​Cj​, asks for an order of nnn jobs on one machine that respects a given acyclic digraph of precedences and minimizes the weighted sum of completion times. It is NP-hard in general (Lawler 1978; Lenstra and Rinnooy Kan 1978), and much of its structural…

11 thms3 active usersReviewed
🏆Completed
Control TheoryDynamical SystemsOperations Research·Captain: mikedeng1

Dynamic Instabilities and Stabilization Methods in Distributed Real-Time Scheduling of Manufacturing Systems 3: Clear-a-Fraction Policies Are Stable From Every Initial State When ρ′ₘ < 1Research Paper

A flexible manufacturing system processes several part types on shared machines, and a machine that switches from one part type to another pays a set-up time. Real-time, distributed scheduling rules for such systems decide locally, at each machine, when to switch and to which buffer. The simplest such rules are clearing policies: a machine keeps working on…

10 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationTheoretical Computer Science·Captain: mikedeng1

Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms III: Every Directed Uniform Multicommodity Flow Problem Has Ω(𝒮/log n) ≤ f ≤ 𝒮Research Paper

Many graph problems in routing, VLSI layout and scheduling ask for a cut that separates a lot of demand while cutting little capacity. For a single commodity, the max-flow min-cut theorem of Ford and Fulkerson says that the largest flow equals the smallest cut. For several commodities sharing one network this equality fails, and the question becomes how far…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisNumerical Analysis·Captain: mikedeng1

A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite Element Approximation 2: Internal Approximations Under (4.1)–(4.3) Have Solutions v_h Converging Strongly to vResearch Paper

An infinite dimensional variational problem can be described by continuous linear operators and convex functionals, yet numerical work needs finite dimensional spaces. The question is whether a solution computed in a finite dimensional approximation still approaches the solution of the original problem when the approximation is refined. Gabay and Mercier's I…

13 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationTheoretical Computer Science·Captain: mikedeng1

Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms II: Every Product Multicommodity Flow Problem with k Commodities Has Ω(𝒮/log k) ≤ f ≤ 𝒮Research Paper

For a single commodity, the Ford–Fulkerson theorem says that the maximum flow between two nodes equals the minimum capacity of a cut separating them. Many routing and partitioning problems involve many source–sink pairs at once, and for those the equality fails: the largest fraction of every demand that can be routed simultaneously can be strictly smaller…

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

Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming 4: Nonquadratic Multiplier Methods for Inequality Constraints Find an Optimal MultiplierResearch Paper

Convex programs with inequality constraints arise when a decision must meet capacity, resource, or performance limits. Their Lagrange multipliers assign a price to each constraint. Finding an optimal multiplier gives a dual certificate and can guide a primal optimization method. Classical quadratic multiplier methods update these prices through a particular…

17 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

Convergence Properties of the Nelder–Mead Simplex Method in Low Dimensions I: In Dimension 1, Both Endpoints Converge to the Minimizer of a Strictly Convex Function When ρχ ≥ 1Research Paper

The Nelder–Mead simplex method (Nelder and Mead, 1965) is one of the most widely used methods for minimizing a function without derivatives. It is the default unconstrained derivative-free minimizer in several numerical libraries (fminsearch in MATLAB, method="Nelder-Mead" in SciPy) and is used routinely in chemistry, engineering and statistics, where the…

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

Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming 3: The Nonquadratic Method of Multipliers for Linear Equality Constraints ConvergesResearch Paper

The method of multipliers (augmented Lagrangian method) of Hestenes and Powell is one of the standard algorithms for constrained convex optimization. Each iteration minimizes the Lagrangian plus a quadratic penalty on the constraint residual, then updates the multiplier estimate. Rockafellar showed in 1976 that this method is the proximal point algorithm…

11 thms3 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOptimization·Captain: mikedeng1

Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming 2: Bregman Proximal Point Sequences Exist When im ∇h Is ℝⁿ, or Is Open and 0 ∈ im TResearch Paper

The proximal point method seeks a zero of an operator by repeatedly solving an implicit equation. For a maximal monotone operator, the ordinary quadratic proximal step is available throughout a Hilbert space. Eckstein's 1993 paper replaces the quadratic penalty with a Bregman function, allowing a step to reflect the geometry of a constrained problem. Before…

14 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Dynamic Pricing and Inventory Control of Substitute Products 3: Optimal Dynamic Prices When the Other Variates Keep Fixed PricesResearch Paper

A retailer that sells a line of substitutable products — sizes, colours or models of one item — over a short season without replenishment must decide how to price each variate as inventory runs down. Customers substitute: when one variate is expensive or sold out, part of its demand moves to the others. Dong, Kouvelis and Tian (M&SOM 2009) model this with a …

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationMarkov Chain+1·Captain: mikedeng1

Linear Programming and Markov Decision Chains 2: Representatives of Average Optimal Stationary Policies Are Optimal Dual Solutions, and Every Optimal Dual Solution Gives an Average Optimal PolicyResearch Paper

A finite Markov decision process may have several recurrent classes under one policy. In that setting, its long-run reward depends on the initial state, and a single stationary distribution does not describe the whole decision problem. Hordijk and Kallenberg developed a linear program with two families of variables to handle this multichain case. Their…

13 thms3 active usersReviewed
🏆Completed
AnalysisHarmonic AnalysisProbability+1·Captain: mikedeng1

Distribution Function Inequalities for Martingales 3: For Brownian Motion Stopped at Any Stopping Time τ, EΦ(X*(τ)) and EΦ(τ^{1/2}) Are ComparableResearch Paper

The size of a martingale can be measured in two ways: by its maximal function, the largest absolute value it reaches, and by a quadratic quantity that records how much it has moved, the square function in discrete time or the elapsed time in the case of Brownian motion. The Burkholder–Davis–Gundy inequalities say that these two measurements are comparable…

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

Planning and Acting in Partially Observable Stochastic Domains: The Witness Theorem, a Set of Useful Policy Trees Is Incomplete iff Replacing One Subtree Improves on It at Some Belief StateResearch Paper

A partially observable Markov decision process (POMDP) models an agent that acts in a stochastic world whose state it cannot see directly. The agent sees only noisy observations. POMDPs are the standard model for planning under uncertainty in robotics, dialogue systems, medical decision making and machine maintenance. The exact finite-horizon theory goes…

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

Residual Life Time at Great Age 5: If |c − ((1 − F)/F′)′| ≤ ε for t ≥ t₀, the Residual Life Normed by (1 − F(t))/F′(t) Is Within ε of Π_{0,c} for t ≥ t₀Research Paper

The residual life time of a lifetime XXX at age ttt is the excess X−tX - tX−t given survival, X>tX > tX>t. How it behaves at great ages is a question in reliability (remaining life of an item that has already lasted long), in insurance and demography (remaining life at old age), and in the peaks-over-threshold method of extreme value statistics, where exceedances over a…

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

Implicit Renewal Theory and Tails of Solutions of Random Equations 1: The Implicit Renewal Theorem — If E|M|^κ = 1 Then P(R > t) ~ C₊t^{−κ} and P(R < −t) ~ C₋t^{−κ}Research Paper

Many stochastic models produce a stationary quantity RRR that solves a random equation R=dΨ(R)R \overset{d}{=} \Psi(R)R=dΨ(R), with Ψ\PsiΨ a random map independent of RRR. The random difference equation R=dQ+MRR \overset{d}{=} Q + MRR=dQ+MR (perpetuities in insurance and finance, the ARCH and GARCH volatility models, random walks in random environments), the Lindley equation …

14 thms3 active usersReviewed
🏆Completed
AnalysisHarmonic AnalysisProbability·Captain: mikedeng1

Distribution Function Inequalities for Martingales 2: Gundy's Decomposition of an L¹-Bounded Martingale, with One Stopping TimeResearch Paper

Many operators of harmonic analysis are bounded on L2L^2L2 by an orthogonality argument but fail to be bounded on L1L^1L1; what survives at p=1p=1p=1 is a weak-type estimate λ P(∣Tf∣>λ)≤c ∥f∥1\lambda\,P(|Tf|>\lambda)\le c\,\|f\|_1λP(∣Tf∣>λ)≤c∥f∥1​. For singular integrals the standard route to such an estimate is the Calderón–Zygmund decomposition, which splits a function at height λ\lambdaλ into a bounded…

5 thms3 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryProbability+1·Captain: mikedeng1

Software Protection and Simulation on Oblivious RAMs: Every Oblivious Simulation of t Steps Makes max{|y|, Ω(t log t)} AccessesResearch Paper

Programs often reveal information through the memory locations they touch, even when the contents of those locations are hidden. An oblivious RAM simulation aims to conceal this access pattern. Goldreich and Ostrovsky studied the cost of doing so for arbitrary RAM programs and showed that the access sequence itself imposes a lower bound on simulation…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+2·Captain: mikedeng1

Inapproximability of Edge-Disjoint Paths and Low Congestion Routing on Undirected Graphs: A Random Hypergraph Instance Gives the Flow Relaxation an Integrality Gap of β₁/(4c) at Congestion c − 1Research Paper

In the edge-disjoint paths problem (EDP) one is given an undirected graph and a list of source–sink pairs, and asks how many pairs can be connected simultaneously by paths that share no edge. Its relaxation EDP with congestion (EDPwC) allows every edge to carry up to a fixed number of paths. Both are central problems of network routing and of approximation…

12 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOperations Research+1·Captain: mikedeng1

Cooperative Fuzzy Games 2: A Game with Side Payments Has a Nonempty Core Iff It Is Balanced, and Then Its Core Is the Core of Its Concave Fuzzy ExtensionResearch Paper

A cooperative game with side payments assigns to each coalition of players the total payoff it can secure on its own and share freely among its members. The core is the set of ways of dividing the payoff of the grand coalition that no coalition can improve upon. It is the basic stability notion of cooperative game theory and of its applications in…

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

Paths, Trees, and Flowers II: Invariance of the Dual — the Outer Vertices O(G) Are Exactly the Vertices Left Exposed by Some Maximum MatchingResearch Paper

A maximum matching of a graph is a largest set of edges no two of which share a vertex. Maximum matchings are rarely unique, and a basic question is which features of them are forced by the graph. J. Edmonds' paper Paths, trees, and flowers (Canad. J. Math. 17 (1965), 449–467) gave the first polynomial-time algorithm for maximum matching in general graphs.…

18 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOperations Research+1·Captain: mikedeng1

Cooperative Fuzzy Games 4: The Fuzzy Core of an Exchange Economy Coincides with Its Set of Walras EquilibriaResearch Paper

The core of an exchange economy is the set of allocations that no group of consumers can improve upon by trading only among themselves. The Walras equilibria (competitive equilibria) are the allocations supported by a price system at which every consumer maximizes preference on a budget set. Every Walras equilibrium is in the core, but for a fixed finite…

6 thms3 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: mikedeng1

Smart "Predict, then Optimize": Under a Continuous, Centrally Symmetric Cost Law Every Minimizer of the SPO+ Risk Equals E[c|x] and Minimizes the SPO RiskResearch Paper

Many decisions are made before their objective coefficients are known. A planner may know the feasible decisions and the form of a linear optimization problem, but must predict its cost vector from available features. Squared prediction error measures how close a forecast is to the eventual coefficients; it need not measure the quality of the decision…

10 thms3 active usersReviewed
Machine LearningOptimizationProbability+1·Captain: mikedeng1

Learning Models with Uniform Performance via Distributionally Robust Optimization 1: The Plug-In Cressie–Read Robust Risk Concentrates at Rate n^(−1/(k*∨2))·√(t + log n) (Theorem 2)Research Paper

A model trained to minimize its average loss EP0[ℓ(θ;X)]\mathbb E_{P_0}[\ell(\theta;X)]EP0​​[ℓ(θ;X)] can perform poorly on subpopulations that are rare under the training distribution P0P_0P0​. Distributionally robust optimization replaces the average loss by its worst case over all distributions QQQ close to P0P_0P0​ in an fff-divergence, which upweights the tail of the loss and controls…

12 thms3 active usersReviewed
PreviousPage 87 of 193Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5215500
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36675464
5NINickrobbins953289156
6VEvebis25800
7FIfizzyinc321715
8SHshivm17500
9SCShuze Chen9455324
10KMkmehltretter82939261

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