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

2051–2075 of 4812
Open1244Completed3568All4812
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Robust Dynamic Programming 3: The Worst-Case Expectation over a Chi-Square Ball Equals a Mean–Standard-Deviation DualResearch Paper

Robust dynamic programming replaces the single transition law of a Markov decision process by a set of laws, and values a policy by its worst-case expected reward over that set. Iyengar (Robust dynamic programming, CORC Tech Report TR-2002-07, 2004; Math. Oper. Res. 30(2), 2005) and Nilim and El Ghaoui (Robust control of Markov decision processes with…

14 thms3 active users
🏆Completed
AnalysisProbabilityRandom Matrix Theory·Captain: mikedeng1

Phase Transition of the Largest Eigenvalue for Nonnull Complex Sample Covariance Matrices 2: Spikes above 1+γ⁻¹ Give √M Fluctuations of the Largest Eigenvalue with Limit G_k, the k×k GUE LawResearch Paper

Sample covariance matrices are the basic object of multivariate statistics: principal component analysis, signal detection and factor models all start from the eigenvalues of S=1M∑k=1My⃗ky⃗k ∗S = \frac1M\sum_{k=1}^M \vec y_k \vec y_k^{\,*}S=M1​∑k=1M​y​k​y​k∗​ computed from MMM samples of an NNN-dimensional vector. When NNN is comparable to MMM, the eigenvalues of SSS no longer approximate those of the…

22 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

A Multiple-Choice Secretary Algorithm with Applications to Online Auctions: The Recursive k-Choice Secretary Algorithm Earns at Least (1 − 5/√k) Times the Sum of the k Largest ValuesResearch Paper

The secretary problem asks how well an online decision maker can do when items arrive one at a time in random order and each must be accepted or rejected on the spot. With a single selection, the classical rule (observe a 1/e1/e1/e fraction, then take the first item better than everything seen) selects the best item with probability about 1/e1/e1/e, and no rule does…

11 thms3 active usersReviewed
Graph TheoryProbabilityStatistics·Captain: mikedeng1

Random Graphs with a Given Degree Sequence 3: With Probability 1 − C(L)n⁻² the β-Model MLE Exists, Is Unique, and Is Within C(L)√(log n/n) of βResearch Paper

Network data often come as a single observed graph, and the simplest summary of a graph is its degree sequence, the list of the numbers of neighbours of its vertices. A statistical model in which the degree sequence is a sufficient statistic is an exponential family on graphs, and the simplest such family is the β-model: each vertex iii carries a parameter …

10 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem: The Integer Points of P1 ∩ P2 Are Exactly the CVRP Solutions, and the Dantzig–Wolfe Master Describes P1 ∩ P2Research Paper

The capacitated vehicle routing problem (CVRP) asks for KKK delivery routes from a depot that serve every client exactly once without exceeding a vehicle capacity, at minimum total length. It was introduced by Dantzig and Ramser in 1959 and is the reference problem of the vehicle routing literature: most exact methods for richer routing models (time windows,…

17 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Mitigating Supply Risk: Dual Sourcing or Process Improvement? 3: Late Commitment Strictly Beats Early Commitment When the Costlier Supplier's Improved Gain Exceeds mz/(θ(1−θ))Research Paper

Firms that buy from unreliable suppliers can protect themselves in two ways: they can spread orders across several suppliers, or they can invest in improving a supplier's reliability, for example through supplier-development programmes or joint process-improvement projects. Wang, Gilland and Tomlin (MSOM 12(3):489–510, 2010) compare the two strategies in a…

8 thms3 active usersReviewed
🏆Completed
Formal VerificationMathematical LogicTheoretical Computer Science·Captain: mikedeng1

Compositional Shape Analysis by Means of Bi-Abduction 1: The Best Abductive Solution for Points-To Symbolic Heaps Is a Computable Disjunction of Symbolic HeapsResearch Paper

Automatic verification of programs that manipulate pointers needs procedure specifications: preconditions saying which part of the heap a procedure touches and postconditions saying what it leaves behind. Writing them by hand does not scale to millions of lines of code. Calcagno, Distefano, O'Hearn and Yang (J. ACM 58(6), 2011) infer them compositionally…

13 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchProbability·Captain: mikedeng1

Linearly Parameterized Bandits 3: For Any Compact Set of Arms, the Uncertainty Ellipsoid Policy Has Regret at Most a₄r‖z‖ + a₅r√T log^{3/2} TResearch Paper

In a linearly parameterized bandit a decision maker repeatedly chooses an arm uuu from a set Ur⊂Rr\mathcal U_r \subset \mathbb R^rUr​⊂Rr and observes a noisy reward whose mean is linear in an unknown vector ZZZ. The model covers problems in which many arms share a few underlying features: products described by a handful of characteristics, prices, or routes whose costs…

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

On Metric Generators of Graphs 1: An Isometry Given on a Strong Metric Generator T of H, With H − T a Forest, Extends to All of H Exactly When H Has a Representation in GResearch Paper

A set of vertices TTT of a graph is a metric generator when every vertex is determined by its vector of distances to the elements of TTT. The minimum size of such a set is the metric dimension, studied in graph theory since the 1970s and surveyed by Chartrand, Eroh, Johnson and Oellermann (Discrete Appl. Math. 2000). Metric generators also appear in…

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

Distributionally Robust Optimization and Its Tractable Approximations 3: The Infimal Convolution of π¹, π², π³ Bounds the Worst Case over the Intersected Families and Improves on EachResearch Paper

Two-stage and multistage stochastic programs ask for decisions that react to uncertainty revealed over time. When the distribution of the uncertainty is known only partially, one optimizes against the worst distribution in a family F\mathbb FF consistent with what is known: a support set, a range for the mean, a covariance matrix, bounds on how fast the tails…

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

A Monotone+Skew Splitting Model for Composite Monotone Inclusions in Duality: The Inexact Primal–Dual Forward–Backward–Forward Iterates Converge Weakly to a Primal and a Dual SolutionResearch Paper

Many problems in convex optimization, variational inequalities, mechanics, traffic equilibrium and signal processing reduce to finding a zero of a monotone operator on a Hilbert space. Frequently that operator is a sum A+L∗∘B∘LA + L^*\circ B\circ LA+L∗∘B∘L of a monotone operator and a monotone operator composed with a linear map and its adjoint, and one also wants the…

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

Solving Semidefinite-Quadratic-Linear Programs Using SDPT3: The HKM and NT Search Directions of Second-Order Cone Programming Are Invariant Under Automorphic ScalingResearch Paper

Second-order cone programming (SOCP) minimizes a linear function over the intersection of an affine subspace with a product of Lorentz cones. It contains convex quadratically constrained programs, robust linear programs with ellipsoidal uncertainty, and many norm-minimization problems, and it is solved in practice by primal–dual interior-point methods. At…

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

Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems: Error √2ΘL/(αN) After N StepsResearch Paper

Monotone variational inequalities (v.i.) cover convex minimization, convex–concave saddle-point problems, Nash equilibria of convex games and complementarity problems. Matrix games and other large saddle-point problems are typical cases. At large scale, first-order methods that use only values of the operator and simple auxiliary minimizations are the…

18 thms3 active users
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Centralized and Competitive Inventory Models with Demand Substitution 2: At Least One Product Is Stocked No Less Under Competition Than Under Centralized ManagementResearch Paper

A retailer that carries several substitutable products, such as brands of the same item, loses part of a customer's demand when the preferred product is out of stock, but not all of it: some customers buy another product instead. How much of each product to stock then depends on the stocking levels of the others. When all products are managed by one…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningReinforcement Learning·Captain: mikedeng1

On the Sample Complexity of Reinforcement Learning III: Non-Stationary Approximate Policy Iteration Is Within 2T Times the Regression Error Averaged over Any Competitor's State-Time DistributionTextbook

Approximate dynamic programming replaces the exact value functions of a Markov decision process by approximations, typically produced by a regression algorithm. The classical guarantees for the resulting policies are stated in the max norm: if every state-action value is estimated to within ε\varepsilonε uniformly over the state space, the greedy policy loses…

19 thms3 active usersReviewed
Linear algebraNumerical AnalysisOptimization·Captain: mikedeng1

The Primal-Dual Active Set Strategy as a Semismooth Newton Method IV: Global Convergence for Small Perturbations of M-MatricesResearch Paper

Obstacle problems, contact problems and control-constrained optimal control problems lead, after discretization, to complementarity systems of the form "find y≤ψy \le \psiy≤ψ and λ≥0\lambda \ge 0λ≥0 with Ay+λ=fAy + \lambda = fAy+λ=f and λi(yi−ψi)=0\lambda_i(y_i - \psi_i) = 0λi​(yi​−ψi​)=0". The primal-dual active set strategy solves such systems by guessing which constraints are active, solving one linear…

10 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchProbability·Captain: mikedeng1

Linearly Parameterized Bandits 2: Under Smooth Best Arm Response, the Phased Exploration and Greedy Exploitation Policy Has Regret at Most a₁(‖z‖ + 1/‖z‖)r√TResearch Paper

In a linearly parameterized bandit, a decision maker repeatedly chooses an arm from a possibly infinite set of vectors and receives a noisy reward whose mean is linear in an unknown parameter. Classical bandit policies treat arms as independent and must try each arm, so their regret grows with the number of arms (Lai and Robbins 1985); in applications such…

13 thms3 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Robust Regression and Lasso 4: ‖b − Ax‖₂ + √n c‖x‖₁ + √n c Equals the Worst Case of √(n·E_μ[(b′ − r′ᵀx)²]) over Box-Constrained Distribution ClassesResearch Paper

The Lasso fits a linear model to data (b,A)(b, A)(b,A) by penalizing the ℓ1\ell_1ℓ1​ norm of the coefficient vector. Xu, Caramanis and Mannor (arXiv:0811.1790) showed that ℓ1\ell_1ℓ1​-regularized regression is exactly a robust regression problem: it minimizes the worst-case residual when every feature column may be disturbed within a norm ball. That reading explains Lasso…

4 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Robust Regression and Lasso 2: When an Absolute Norm Bounds the Column Disturbance Norms, Robust Regression Is Regression Regularized by the Dual Norm, ‖b − Ax‖ₐ + l‖x‖*ₛResearch Paper

Robust regression guards a linear model against errors in the data matrix. The observations b∈Rnb \in \mathbb R^nb∈Rn are fitted by AxAxAx, but the features (the columns a1,…,ama_1,\dots,a_ma1​,…,am​ of AAA) are only known up to a disturbance ΔA\Delta AΔA from an uncertainty set U\mathcal UU. The robust estimator minimizes the worst-case residual,

5 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Reliable Facility Location Design Under the Risk of Disruptions 4: The Fixed-Probability Reformulation (RRSP) Lower-Bounds the Relaxed SubproblemResearch Paper

Facility networks fail: plants close after floods, distribution centres lose power, suppliers go bankrupt. The reliable uncapacitated facility location problem (RUFL) of Cui, Ouyang and Shen (UCTC-FR-2010-02, February 2010; published as Operations Research 58(4), 2010, doi:10.1287/opre.1090.0801) chooses which facilities to open and, for every customer, an…

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

Distributionally Robust Optimization and Its Tractable Approximations 2: Under a Mean Set and a Known Covariance, the Bound π² Equals the Worst-Case Expected Positive PartResearch Paper

Many operations models contain terms of the form EP((r0+r′ζ~)+)E_{\mathbb P}\big((r^0 + r'\tilde\zeta)^+\big)EP​((r0+r′ζ~​)+): expected shortfall or overflow of an affine function of an uncertain vector. Inventory and newsvendor costs, penalties for violated soft constraints, and the Conditional Value-at-Risk of a linear decision rule all reduce to it. In practice the distribution …

8 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

On the Rate of Convergence of Optimal Solutions of Monte Carlo Approximations of Stochastic Programs 3: For Finite Polyhedral Problems the SAA Optimal Set Fails to Be a Face Exponentially RarelyResearch Paper

Stochastic programs of the form min⁡x∈ΘEP h(x,ω)\min_{x\in\Theta}\mathbb E_P\,h(x,\omega)minx∈Θ​EP​h(x,ω) are rarely solvable exactly, because the expectation is an integral over a large or continuous scenario space. The standard remedy is sample average approximation (SAA), also called the Monte Carlo or sample path method: draw an i.i.d. sample ω1,…,ωN\omega^1,\dots,\omega^Nω1,…,ωN from PPP and…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Convex Quadratic and Semidefinite Programming Relaxations in Scheduling III: Optimal Nonpreemptive Schedules Are Within 3 of Preemptive Ones for R | rᵢⱼ | Σ wⱼCⱼ, Within 2 Without Release DatesResearch Paper

In machine scheduling, preemption means that a job may be interrupted and resumed later, possibly on a different machine. Allowing it can only lower the optimal cost, and a basic question for every scheduling model is how much it can lower it: the ratio between the best nonpreemptive and the best preemptive schedule, often called the power of preemption.…

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

How Bad is Selfish Routing? 4: With Polynomial Latencies of Degree p and Nonnegative Coefficients the Cost of a Nash Flow Is at Most p + 1 Times the Optimal CostResearch Paper

In a road or communication network carrying a large population of users, each user picks a route that is fastest for itself given the congestion caused by everyone else. The resulting traffic pattern, a Wardrop or Nash equilibrium, need not minimize the total travel time: Braess's paradox shows that adding a road can make every user slower. Transportation…

10 thms3 active usersReviewed
AlgebraAlgebraic GeometryConvex Optimization+1·Captain: mikedeng1

Semidefinite Programming Relaxations for Semialgebraic Problems 1: A Polynomial System Has No Real Solution if and only if Its Degree-d Positivstellensatz SDP Is Feasible for All Large dResearch Paper

Deciding whether a system of real polynomial equations, inequations and inequalities has a solution is the basic feasibility question behind nonconvex quadratic programming, polynomial optimization, robustness analysis in control, and combinatorial relaxations. Over the complex numbers, Hilbert's Nullstellensatz turns infeasibility into an algebraic…

13 thms3 active usersReviewed
PreviousPage 83 of 193Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5262500
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36975536
5NINickrobbins953290156
6VEvebis25800
7FIfizzyinc321735
8SHshivm17520
9KMkmehltretter821002265
10SCShuze Chen9455327

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