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

326–350 of 4812
Open1285Completed3527All4812
🏆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
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Eigenvalues and Expanders: A Regular Bipartite Graph Is a Strong Expander If and Only If λ(G) Is Bounded Away from 0Research Paper

Expander graphs are sparse graphs in which every set of vertices has many neighbours. Families of them with bounded degree and expansion bounded away from zero are a basic tool of theoretical computer science: they are the main component of the sorting network of Ajtai, Komlós and Szemerédi (AKS 1983), the building block of superconcentrators and other…

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

Analysis of Thompson Sampling for the Multi-armed Bandit Problem 1: Logarithmic Regret for Two ArmsResearch Paper

Thompson Sampling (TS) is the oldest heuristic for the stochastic multi-armed bandit problem: it was proposed by Thompson in 1933 (Biometrika 25) and is used in practice for online advertising and recommendation, where it often performs as well as or better than upper-confidence-bound methods (Chapelle and Li, NIPS 2011; Scott 2010). Until 2012 its…

12 thms5 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research+1·Captain: mikedeng1

Understanding and Using Linear Programming IV: The Duality Theorem and Three Proofs of the Farkas LemmaTextbook

Every linear program comes with a second linear program, its dual, whose feasible solutions certify bounds on the optimum of the first. The duality theorem of linear programming says that these certificates are perfect: when both programs are feasible, the best bound equals the optimum. The theorem underlies the analysis of the simplex method, sensitivity…

14 thms5 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingLinear algebra+3·Captain: mikedeng1

Bellman's Dynamic Programming IX: Markovian Decision Processes and the Maximal Perron RootTextbook

Chapter XI of Richard Bellman's Dynamic Programming (Princeton University Press, 1957; DOI 10.2307/j.ctv1nxcw0f) studies decision processes whose state is a vector of nonnegative quantities, for example the probabilities that a system is in each of NNN states, or the stocks of NNN commodities, and whose transitions are linear maps chosen stage by stage by a…

13 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

A Dynamic Near-Optimal Algorithm for Online Linear Programming I: The Competitive Ratio of the Dynamic Learning AlgorithmResearch Paper

Many resource-allocation problems are decided one request at a time: a seller of airline seats or hotel nights, an ad platform allocating advertiser budgets, a network operator admitting bandwidth requests. Each request asks for a bundle of resources and offers a price. It must be accepted or rejected on arrival, before the later requests are seen. The onlin…

13 thms5 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Minimization Methods for Non-Differentiable Functions III: Convergence of the Normalized Subgradient Method with Divergent-Series StepsizesTextbook

Many optimization problems of operations research have objectives that are convex but not differentiable: Lagrangian duals of integer and combinatorial programs, maxima of finitely many affine or smooth functions, penalty functions for systems of inequalities, and the value functions produced by decomposition. For such functions the gradient method and…

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

Introduction to the Scenario Approach I: The Violation Distribution of the Scenario SolutionTextbook

Many design problems in control, finance and operations research are convex programs with uncertain constraints: a decision θ\thetaθ must satisfy θ∈Θδ\theta\in\Theta_\deltaθ∈Θδ​ for a parameter δ\deltaδ that is not known in advance. Enforcing the constraint for every possible δ\deltaδ (robust optimization) is often intractable or too conservative, and a chance-constrained…

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

An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem II: Geometric Grouping with Residual LP RoundingResearch Paper

One-dimensional bin packing asks for the fewest unit-capacity bins that hold a given list of items with sizes in (0,1)(0,1)(0,1). Deciding whether two bins suffice is NP-hard (it contains the partition problem), so no polynomial-time algorithm guarantees a ratio below 3/23/23/2 unless P = NP. The natural question is therefore asymptotic: how small can the additive error …

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

Selected Topics in Column Generation I: Discretization — Every Integer Point of a Rational Polyhedron Is a Generating Integer Point Plus an Integer Combination of Integer RaysResearch Paper

Dantzig–Wolfe decomposition and column generation solve large integer programs by replacing a set of "easy" constraints with a description of its feasible points, and then pricing out the points one at a time. For linear programs this rests on the Minkowski–Weyl representation: every point of a polyhedron is a convex combination of its extreme points plus a…

5 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability+1·Captain: mikedeng1

Competitive Randomized Algorithms for Nonuniform Problems III: The Optimal Randomized Two-Server Ratio on the 1-d-d Isosceles TriangleResearch Paper

The k-server problem of Manasse, McGeoch and Sleator (J. Algorithms 11 (1990)) asks how kkk mobile servers in a metric space should respond, on-line, to a sequence of requests at points of the space, each of which must be covered by a server. It is the central model of on-line computation: paging is the special case of a uniform metric, and many caching and…

9 thms5 active usersReviewed
🏆Completed
AnalysisFunctional AnalysisPartial Differential Equations·Captain: mikedeng1

Notes on Partial Differential Equations IV: Extension, Trace and the Rellich–Kondrachov TheoremTextbook

Existence theory for elliptic, parabolic and nonlinear PDEs mostly runs through one argument: build approximate solutions, bound them in a Sobolev norm, extract a convergent subsequence, and pass to the limit. The extraction step needs a compact embedding: a bound on derivatives must buy convergence of the functions themselves in a weaker norm. On a bounded…

88 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research+2·Captain: mikedeng1

Optimal Best Arm Identification with Fixed Confidence IV: Asymptotic Optimality of the Track-and-Stop StrategyResearch Paper

In best arm identification with fixed confidence, a learner samples KKK unknown distributions (arms) sequentially and must, as early as possible, name the arm with the largest mean, while being wrong with probability at most a prescribed risk δ\deltaδ. The problem models adaptive A/B/n testing, clinical and simulation-based selection among alternatives, and the…

17 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research+2·Captain: mikedeng1

Optimal Best Arm Identification with Fixed Confidence I: Non-Asymptotic Lower Bound on the Sample ComplexityResearch Paper

Best arm identification with fixed confidence is the pure-exploration counterpart of the multi-armed bandit problem. A learner faces KKK unknown reward distributions ("arms"), samples them sequentially, and must stop and name the arm with the largest mean, being wrong with probability at most a prescribed δ\deltaδ. The question is how many samples this…

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

On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities III: Uniform Convergence and the Entropy per ObservationResearch Paper

Estimating a probability by the relative frequency of the event in an independent sample is justified for one event by the law of large numbers. Statistics and learning theory need more: the frequencies of a whole class of events SSS must approach their probabilities simultaneously, so that a quantity chosen after looking at the data (the empirical risk…

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

Applied Combinatorics I: Graph Theory and Dirac's Hamiltonicity TheoremTextbook

Graphs are the most basic combinatorial model of pairwise relations: road networks, frequency interference between radio stations, schedules, circuit layouts. Chapter 5 of Keller and Trotter's Applied Combinatorics (appliedcombinatorics.org, CC BY-SA 4.0) introduces the vocabulary of graph theory and proves its first structural theorems: when a graph can be…

12 thms5 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research+1·Captain: Shuze Chen

Discrete Convex Analysis XXV: L-Convex Functions via Minimizer PolyhedraTextbook

Chapter 5 characterized L-convex sets — sublattice-closed, translation-periodic subsets of ZV\mathbb Z^VZV — and showed they interact cleanly with integral convexity. Chapter 7 asks the functional analogue: which functions on the integer lattice deserve to be called convex in the "L" sense, and how do they relate back to L-convex sets? This mission (continuing…

41 thms5 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOperations Research·Captain: mikedeng1

On the Maximal Monotonicity of Subdifferential Mappings II: Subdifferentials Are Exactly the Maximal Cyclically Monotone Operators, Unique up to an Additive ConstantResearch Paper

A differentiable convex function on Rn\mathbb{R}^nRn is determined, up to an additive constant, by its gradient, and a vector field is a gradient of a convex function exactly when it satisfies a monotonicity condition along closed cycles. Convex analysis and optimization need the same statement for nonsmooth and extended-valued functions on infinite-dimensional…

16 thms5 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOperations Research+2·Captain: mikedeng1

Dual Stochastic Dominance and Related Mean-Risk Models 2: Mean–Gini Optimal Portfolios Exist and Are SSD-EfficientResearch Paper

Portfolio selection and other decisions under risk are routinely solved as mean–risk models: maximize the expected outcome minus a multiple of a risk measure over the feasible set. Such a model is computationally convenient, but it is only defensible if its answers agree with the preferences of risk-averse decision makers. The standard formal expression of…

13 thms5 active usersReviewed
🏆Completed
AnalysisCalculus of VariationsFunctional Analysis+1·Captain: mikedeng1

Notes on Partial Differential Equations V: Weak Solutions of Elliptic PDEs and the Fredholm AlternativeTextbook

Second-order elliptic equations in divergence form, such as −∇⋅(A∇u)+b⋅∇u+cu=f-\nabla\cdot(A\nabla u) + b\cdot\nabla u + cu = f−∇⋅(A∇u)+b⋅∇u+cu=f, model steady diffusion, electrostatics in inhomogeneous media and linear elasticity. They are also the stationary part of every parabolic and hyperbolic problem studied later in the same notes. When the coefficients are only bounded and measurable,…

14 thms5 active usersReviewed
🏆Completed
AnalysisControl TheoryDynamical Systems+2·Captain: mikedeng1

Generalized Gradients and Applications II: Flow-Invariant Sets of Lipschitz Differential InclusionsResearch Paper

A closed set F⊆RnF\subseteq\mathbb R^nF⊆Rn is flow-invariant for a dynamical system when every trajectory that starts in FFF stays in FFF. Invariance of sets underlies state constraints in optimal control, safety certificates for controlled systems, comparison and maximum principles for differential equations, and the positivity of solutions of kinetic and population…

17 thms5 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: mikedeng1

Limits of Permutation Sequences II: Convergence Is Equivalent to Being Cauchy in the Rectangular DistanceResearch Paper

For dense graphs, convergence of subgraph densities was shown by Lovász and Szegedy (2006) to have graphons as limit objects, and Borgs, Chayes, Lovász, Sós and Vesztergombi (2008) proved that the same convergence is metric: a graph sequence converges exactly when it is Cauchy in the cut distance. The metric view is what makes the space of graphons compact…

23 thms5 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningProbability+2·Captain: mikedeng1

The Power of Convex Relaxation: Near-Optimal Matrix Completion II: Exact Nuclear-Norm Recovery from Nearly Minimally Many EntriesResearch Paper

Many data sets are large matrices of which only a small fraction of the entries is observed, and of which the underlying object is believed to have low rank: user–item rating tables in collaborative filtering, distance matrices in sensor-network localization, and measurement matrices in structure-from-motion. Matrix completion asks when the missing entries…

22 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: mikedeng1

Improved Algorithms for Linear Stochastic Bandits II: Constant High-Probability Regret of UCB(δ)Research Paper

The stochastic multi-armed bandit is the basic model of sequential decision making under uncertainty: a learner repeatedly chooses one of ddd actions, observes a noisy reward for the chosen action only, and must balance exploring poorly known actions against exploiting the one that currently looks best. It underlies adaptive clinical trials, online…

6 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Disjunctive Programming XII: Intersection Cuts, Generalized Intersection Cuts, and Lift-and-Project CutsTextbook

Intersection cuts (Balas, 1971) are the founding construction of cutting-plane theory for mixed 0-1 and mixed-integer programs: given a fractional LP solution xˉ\bar xxˉ and a convex region SSS around it known to contain no feasible integer point, the hyperplane through the points where SSS's boundary meets the extreme rays of the LP cone at xˉ\bar xxˉ cuts off xˉ\bar xxˉ w…

14 thms5 active users
PreviousPage 14 of 193Next

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