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

826–850 of 3527
Open1285Completed3527All4812
🏆Completed
Convex OptimizationMachine LearningOptimization+2·Captain: mikedeng1

Learnability, Stability and Uniform Convergence II: Tikhonov-Regularized ERM Learns Convex Lipschitz Stochastic Optimization in Hilbert Space with High ProbabilityResearch Paper

Statistical learning theory asks when a rule that sees only an i.i.d. sample z1,…,zmz_1,\dots,z_mz1​,…,zm​ from an unknown distribution DDD can return a hypothesis whose expected loss is close to the best possible. In supervised classification the classical answer is uniform convergence: learnability holds exactly when empirical risks converge to expected risks uniformly…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Three Partition Refinement Algorithms 2: Refining by the Smaller HalfResearch Paper

Many equivalence problems on finite structures reduce to computing the coarsest partition of a finite set that is compatible with a relation. Deciding whether two states of a finite labelled transition system are bisimilar, testing congruence of finite-state processes in Milner's calculus of communicating systems (CCS), and minimizing a deterministic finite…

12 thms4 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingOperations Research+1·Captain: mikedeng1

Robust Control of Markov Decision Processes with Uncertain Transition Matrices 1: Perfect Duality and the Robust Dynamic Programming Recursion for Finite-Horizon MDPsResearch Paper

A Markov decision process (MDP) is solved by dynamic programming once its transition probabilities are known. In practice they are estimated from data, and the optimal policy of an MDP can be sensitive to estimation error: a policy computed from point estimates may perform much worse under the true transition matrices. Nilim and El Ghaoui (Oper. Res. 53(5),…

11 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization+1·Captain: mikedeng1

A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers: Error Bounds under Decomposability and Restricted Strong ConvexityResearch Paper

High-dimensional statistics studies estimation when the number of parameters ppp is comparable to, or larger than, the number of observations nnn. The standard estimators in this regime are regularized M-estimators: minimise an empirical loss plus a penalty that encodes structure, such as the Lasso (ℓ1\ell_1ℓ1​ penalty, sparse vectors), the group Lasso (block norms,…

5 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: Shuze Chen

Disjunctive Programming XVI: Unions of Upper Monotone Polytopes and PolymatroidsTextbook

This mission is the sixteenth and last of the Disjunctive Programming series, and its goal theorem is the book's own closing result. The chapter's arc closes a loop opened at the very start of the book: Theorem 2.1 (02a-convex-hull) gave the convex hull of a union of polyhedra in the same space via lifting; this chapter's Theorem 13.13 (not drafted in this…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: Shuze Chen

Disjunctive Programming XV: Dominants of Polytopes and Upper SeparationTextbook

Many real-world disjunctive models are not unions of polyhedra in a single shared space, but unions of polyhedra in different spaces linked by a logical implication: some action affecting one set of entities has consequences for another. Balas's treatment of such models (§17 of the book, following [17]) reduces to understanding a single auxiliary object…

8 thms4 active users
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Disjunctive Programming XIV: Disjunctive Cuts from the V-Polyhedral RepresentationTextbook

The lift-and-project cut-generating LP (CGLP) is the workhorse of the book's cutting-plane machinery, but its number of variables grows with qqq, the number of terms in the disjunction — a real computational cost for disjunctions with many terms. An alternative representation of the same disjunctive hull, built from vertices and extreme rays rather than from…

7 thms4 active users
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Disjunctive Programming XIII: Monoidal Cut Strengthening and the Gomory Mixed-Integer CutTextbook

The Gomory mixed-integer (GMI) cut is the single most widely deployed cutting plane in practical mixed-integer programming: every commercial solver generates it, from a simplex tableau row, essentially for free. Yet the GMI cut is not the strongest cut derivable from the same row: once a subset of the variables is known to be integer-constrained, that…

8 thms4 active users
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Disjunctive Programming XI: The Cut-Generating LP Under a Ray NormalizationTextbook

Lift-and-project (L&P) cuts strengthen the linear relaxation of a mixed 0-1 program by separating a fractional point from the convex hull of a disjunction such as xk≤0∨xk≥1x_k \le 0 \lor x_k \ge 1xk​≤0∨xk​≥1. Generating an optimal L&P cut means solving the cut-generating linear program (CGLP), a linear program lifted to a space with one new pair of variables per constraint of…

8 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Disjunctive Programming X: Solving the Cut-Generating LP on the Simplex TableauTextbook

Chapter 8 established an exact correspondence between lift-and-project cuts and simple disjunctive cuts, but its practical payoff is what this chapter develops: the cut-generating LP (CGLP)_k never needs to be formulated or solved on its own. Every pivot of (CGLP)_k can instead be mimicked directly on the much smaller simplex tableau of the original LP…

9 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Disjunctive Programming VIII: Nonlinear Higher-Dimensional RepresentationsTextbook

Chapter 2's convex-hull machinery gives an exact, finitely-generated linear description of a disjunctive set's convex hull, but for a mixed 0-1 program with ppp binary variables that description lives in a space with roughly pnpnpn auxiliary variables — one full lift per disjunction. This chapter surveys the alternative nonlinear higher-dimensional constructions…

16 thms4 active users
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Disjunctive Programming VII: Lift-and-Project Cuts for Mixed 0-1 ProgramsTextbook

A mixed 0-1 program's feasible region is a disjunctive set built from the split disjunctions xj≤0∨xj≥1x_j \le 0 \lor x_j \ge 1xj​≤0∨xj​≥1, one per binary variable — a special case general enough that Chapter 2's convex-hull machinery applies directly, yet structured enough to produce closed-form cutting planes efficiently. The resulting lift-and-project (L&P) cuts, generated…

8 thms4 active users
🏆Completed
Convex OptimizationFunctional AnalysisOperations Research·Captain: mikedeng1

Proximité et dualité dans un espace hilbertien II: Proximal Maps Are the Nonexpansive Subgradient Selections of Convex FunctionsResearch Paper

The proximal map of a convex function is the basic building block of proximal-point, forward–backward, Douglas–Rachford and ADMM methods, which are used throughout large-scale convex optimization, signal processing and operator splitting. All of these methods treat prox⁡g\operatorname{prox}_gproxg​ as a nonexpansive operator and use the fact that it is a gradient. The…

12 thms4 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Adversarially Robust Generalization Requires More Data 1: A Robust-Error Lower Bound in the Gaussian ModelResearch Paper

Classifiers trained to high standard accuracy on image benchmarks can be made to fail by perturbations of the input that are small in the ℓ∞\ell_\inftyℓ∞​ norm (Szegedy et al., 2014; Goodfellow et al., 2015). Adversarial training reaches high robust accuracy on the training set, but on CIFAR10 the robust accuracy on held-out data is much lower than on the…

8 thms4 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOperations Research·Captain: mikedeng1

Proximité et dualité dans un espace hilbertien I: Moreau's Decomposition into Proximal Points of a Function and Its DualResearch Paper

Proximal maps are the basic building block of first-order methods for nonsmooth convex optimization: the proximal point algorithm, forward–backward splitting (ISTA/FISTA), Douglas–Rachford splitting and ADMM all proceed by evaluating maps of the form z↦argmin⁡u[12∥u−z∥2+f(u)]z \mapsto \operatorname{argmin}_u \big[\tfrac12\|u - z\|^2 + f(u)\big]z↦argminu​[21​∥u−z∥2+f(u)]. The notion and its name come from…

8 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

A Branch and Bound Algorithm for the Generalized Assignment Problem: The Knapsack Penalty Bound Equals the Lagrangean Bound at Second-Smallest CostsResearch Paper

The generalized assignment problem (GAP) asks for the cheapest way to give each of nnn tasks to exactly one of mmm agents when every agent has a limited amount of a resource and different agents consume different amounts of it for the same task. It models assigning jobs to machines or computers, software tasks to programmers, commercials to time slots, and…

10 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Disjunctive Programming II: The Convex Hull of a Disjunctive Set via Lifting and ProjectionTextbook

Convexity is what makes optimization tractable: a linear program's feasible region is convex, and this single fact underwrites the simplex method, LP duality, and everything built on top of them. Integer and disjunctive programs have no such luck — their feasible regions are unions of polyhedra, and a union of convex sets is generally not convex. If the conv…

8 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization+1·Captain: mikedeng1

Cones of Matrices and Set-Functions and 0–1 Optimization II: One Round of N on the Stable Set Polytope Gives Exactly the Odd Hole ConstraintsResearch Paper

The stable set problem (vertex packing) asks for a largest set of pairwise non-adjacent nodes of a graph. It is NP-hard, and its polyhedral study, the description of the stable set polytope STAB(G)\mathrm{STAB}(G)STAB(G) by linear inequalities, is one of the most studied topics of polyhedral combinatorics. Classes of valid inequalities (clique, odd hole, odd antihole,…

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

Strategic Capacity Rationing to Induce Early Purchases: Rationing Is Optimal When the Valuation Bound Reaches U_c, Low-Price-Only OtherwiseResearch Paper

Retailers of seasonal goods sell at a full price first and mark down later. Customers who know this can wait for the markdown, and a firm that always has stock left for the markdown teaches them to wait. One remedy is to stock less than the low-price market would absorb, so that a customer who waits risks not getting the good at all. Liu and van Ryzin (Manag…

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

Advance Demand Information, Price Discrimination, and Preorder Strategies: When Preorder Profit Increases with Demand CorrelationResearch Paper

Firms that sell new products (consoles, books, films) often take preorders before release. A preorder serves two purposes at once. It lets the firm charge early adopters a different price from later buyers, a form of price discrimination, and the number of preorders is advance demand information: an early signal of how large regular-season demand will be.…

10 thms4 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Pattern Search Algorithms for Bound Constrained Minimization: Generalized Pattern Search Drives the Projected Stationarity Measure to ZeroResearch Paper

Pattern search methods minimize a function f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R by comparing values of fff at points of a structured set of trial points, without evaluating or approximating derivatives. Coordinate search and the method of Hooke and Jeeves (Hooke–Jeeves 1961) are the classical members of the family. Such methods remain in use when derivatives are…

21 thms4 active users
🏆Completed
Information TheoryOperations ResearchOptimization+1·Captain: mikedeng1

Worst-Case Value-At-Risk and Robust Portfolio Optimization: A Conic Programming Approach 2: Closed Form of the Entropy-Constrained Worst-Case VaRResearch Paper

Value-at-Risk (VaR) is the loss level that a portfolio exceeds with probability at most ε\varepsilonε. It is the standard risk measure of banking regulation, and its classical computation assumes Gaussian returns: for a Gaussian return vector with mean x^\hat xx^ and covariance Γ\GammaΓ it equals −Φ−1(ε)w⊤Γw−x^⊤w-\Phi^{-1}(\varepsilon)\sqrt{w^\top\Gamma w} - \hat x^\top w−Φ−1(ε)w⊤Γw​−x^⊤w, where …

9 thms4 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOptimization·Captain: mikedeng1

Strong Convergence of a Proximal-Type Algorithm in a Banach Space: The Algorithm Converges Strongly to the Generalized Projection of x0 onto the Zeros of a Maximal Monotone OperatorResearch Paper

Many problems in optimization and variational analysis reduce to finding a zero of a maximal monotone operator TTT: minimizers of a proper convex lower semicontinuous function are the zeros of its subdifferential, and saddle points and solutions of variational inequalities are zeros of associated monotone operators. The classical tool is Rockafellar's proximal…

13 thms4 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraOperations Research+1·Captain: mikedeng1

Robust Solutions to Uncertain Semidefinite Programs III: Quadratic Growth and Uniqueness of the Robust SDP SolutionResearch Paper

A semidefinite program (SDP) minimizes a linear objective cTxc^TxcTx subject to a linear matrix inequality F(x)=F0+∑ixiFi⪰0F(x) = F_0 + \sum_i x_i F_i \succeq 0F(x)=F0​+∑i​xi​Fi​⪰0. When the data FiF_iFi​ are uncertain, El Ghaoui, Oustry and Lebret (SIAM J. Optim. 9(1), 1998) proposed to optimize against the worst case over a norm-bounded family of perturbations: the robust SDP. Their Theorem 3.1 shows…

10 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Integrating Replenishment Decisions with Advance Demand Information I: The Myopic Order-Up-To Level Is Optimal When Observed Demand Beyond the Protection Period Is LargeResearch Paper

Many firms learn part of future demand before it has to be served: customers place orders days or weeks ahead of the date they need the goods, or commit to delivery dates in contracts. Advance demand information of this kind reduces the uncertainty the inventory manager has to protect against, and the question is how replenishment decisions should use it.…

15 thms4 active usersReviewed
PreviousPage 34 of 142Next

Top contributors

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