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.

3566 completed missions

Missions

2201–2225 of 3566
Open1246Completed3566All4812
🏆Completed
Convex OptimizationLinear OptimizationOperations Research+1·Captain: mikedeng1

Cones of Matrices and Set-Functions and 0–1 Optimization I: n Rounds of the Lovász–Schrijver N Operator Give the 0–1 HullResearch Paper

A 0–1 integer program asks for the best 0–1 vector satisfying a system of linear inequalities. Its linear relaxation is easy to optimize over, but the relaxation is usually much larger than the convex hull of the 0–1 solutions. Lift-and-project methods close this gap systematically: they lift the relaxation to a higher-dimensional space, add constraints…

8 thms3 active usersReviewed
🏆Completed
Control TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Supervisory Control of a Class of Discrete Event Processes I: Minimally Restrictive Supervisors Exist iff the Supremal Controllable Legal Sublanguage Contains the Minimal Acceptable LanguageResearch Paper

Manufacturing cells, communication protocols, traffic systems and database transaction managers are naturally described not by differential equations but by sequences of discrete events: a machine starts, a part arrives, a message is lost. Ramadge and Wonham's 1987 paper (SIAM J. Control Optim. 25(1)) set up a control theory for such systems in which the…

15 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear algebra+2·Captain: mikedeng1

Approximating Clique-Width and Branch-Width: Well-Linked Sets Certify Clique-WidthResearch Paper

Clique-width is a graph parameter introduced by Courcelle and Olariu (Discrete Appl. Math. 101 (2000)) that measures how far a graph is from being built by a few labelled operations. Every problem expressible in monadic second-order logic with quantification over vertices and vertex sets (MSO1_11​) can be solved in linear time on graphs given together with a…

14 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Approximation Algorithms for Combinatorial Problems V: The Overlap-Ratio Greedy C2 Is Within 1 + ln k of the Least-Overlap Cover on EC(k)Research Paper

David S. Johnson's 1974 paper Approximation Algorithms for Combinatorial Problems (J. Comput. System Sci. 9 (1974) 256–278) was one of the first systematic worst-case analyses of polynomial-time heuristics for NP-complete optimization problems. Its Section 5 proves the harmonic bound ∑j=1k1/j\sum_{j=1}^k 1/j∑j=1k​1/j for the greedy algorithm on minimum-cardinality set…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear algebraTheoretical Computer Science·Captain: mikedeng1

Sparse Approximate Solutions to Linear Systems 2: An Exact Cover by 3-Sets Exists iff Its Incidence System Has a 1/2-Approximate Solution with at Most m/3 NonzerosResearch Paper

Many problems in signal processing, statistics and function interpolation ask for a solution of a linear system Ax≈bAx\approx bAx≈b that uses as few columns of AAA as possible: a sparse approximate solution. Natarajan's 1995 paper Sparse Approximate Solutions to Linear Systems (SIAM J. Comput. 24(2):227–234) was motivated by radial basis interpolation, where each…

6 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchStochastic Systems·Captain: mikedeng1

Jobshop-Like Queueing Systems: The Equilibrium Distribution with State-Dependent Arrival and Service RatesResearch Paper

A jobshop is a factory in which each job visits a sequence of machine groups, the sequence differing from job to job. J. R. Jackson's 1963 paper Jobshop-Like Queueing Systems (Management Science 10(1), 131–142) models such a shop as a network of queues and computes its long-run distribution of queue lengths in closed form. It generalizes his 1957 paper Netwo…

6 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Scenario Reduction Algorithms in Stochastic Programming III: The Minimal Reduction Distance of a Regular Ternary Scenario TreeResearch Paper

Multistage stochastic programs are solved on a finite scenario tree: a discrete probability distribution whose support points are paths of a random process. Realistic trees have far too many scenarios for the resulting optimization problem, so practitioners reduce the tree, keeping nnn of its NNN scenarios and redistributing the probability of the deleted ones.…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Scenario Reduction Algorithms in Stochastic Programming II: The Minimal Reduction Distance of a Regular Binary Scenario TreeResearch Paper

Multistage stochastic programs are solved on a finite scenario tree, a discrete probability measure whose atoms are paths of a stochastic process. The size of the deterministic equivalent grows with the number of scenarios, so practitioners replace the original measure P=∑i=1NpiδωiP=\sum_{i=1}^N p_i\delta_{\omega_i}P=∑i=1N​pi​δωi​​ by a measure supported on n<Nn<Nn<N of its scenarios.…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimal TransportOptimization·Captain: mikedeng1

Scenario Reduction Algorithms in Stochastic Programming I: Fast Forward Selection Realizes the Forward Selection PrincipleResearch Paper

Multistage and two-stage stochastic programs are solved numerically on a discrete probability distribution: a finite set of scenarios ω1,…,ωN\omega_1,\dots,\omega_Nω1​,…,ωN​ with probabilities p1,…,pNp_1,\dots,p_Np1​,…,pN​. The size of the resulting optimization problem grows with NNN, and scenario sets produced by sampling or by historical data are often far too large to be solved…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOperations Research+1·Captain: mikedeng1

Golden Ratio Algorithms for Variational Inequalities I: The Golden Ratio Algorithm with a Fixed Step Converges to a Solution of a Monotone Variational InequalityResearch Paper

A monotone variational inequality asks for a point at which a monotone operator and a convex function are in equilibrium. It unifies convex minimization (where FFF is a gradient), convex–concave saddle-point problems (where FFF is the skew gradient of a Lagrangian), Nash equilibria of monotone games, and complementarity problems in economics and traffic…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryNumber Theory+1·Captain: mikedeng1

Fast Algorithms for Finding Nearest Common Ancestors II: Nearest Common Ancestors in a Complete Binary Tree by Symmetric-Order ArithmeticResearch Paper

The nearest common ancestor (nca) problem asks, for a fixed rooted tree and a sequence of vertex pairs (v,w)(v, w)(v,w), for the deepest vertex that is an ancestor of both. It is a basic step in suffix-tree string algorithms and is equivalent to range-minimum queries (Bender, Farach-Colton, 2000). Harel and Tarjan, Fast Algorithms for Finding Nearest Common Ancestors,…

11 thms3 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: mikedeng1

Fast Algorithms for Finding Nearest Common Ancestors I: A Lower Bound for Pointer MachinesResearch Paper

The nearest common ancestor problem asks, for a rooted tree and two of its vertices xxx and yyy, for the deepest vertex that is an ancestor of both, written nca⁡(x,y)\operatorname{nca}(x,y)nca(x,y). It appears as a subroutine in string algorithms (suffix trees), in graph algorithms (path queries, dominators) and in the analysis of set-union structures. Aho, Hopcroft and Ullman (…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningNumerical Analysis+1·Captain: mikedeng1

Proximal Newton-Type Methods for Minimizing Composite Functions II: Local Linear and Superlinear Convergence of the Inexact Proximal Newton MethodResearch Paper

Many estimation problems in statistics, signal processing and bioinformatics minimize a composite function f=g+hf = g + hf=g+h: a smooth convex loss ggg plus a convex but nonsmooth penalty or constraint hhh, such as the lasso's ℓ1\ell_1ℓ1​ norm or the indicator of a convex set. Proximal Newton-type methods handle such problems by minimizing, at each iterate xkx_kxk​, a model …

9 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization+1·Captain: mikedeng1

A New Approach to the Maximum-Flow Problem 2: The Nonsaturating-Push Bound for FIFO Push-RelabelResearch Paper

The maximum-flow problem asks how much of a commodity can be sent from a source to a sink through a network whose edges carry capacities. It is a basic model of operations research. Transportation, scheduling, bipartite matching and image segmentation reduce to it, and it is the inner step of many combinatorial algorithms.

10 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningNumerical Analysis+1·Captain: mikedeng1

Proximal Newton-Type Methods for Minimizing Composite Functions I: Proximal Quasi-Newton Methods Converge Q-Superlinearly under the Dennis–Moré CriterionResearch Paper

Many estimation problems in statistics, machine learning and signal processing minimize a composite function, the sum of a smooth loss and a convex but nonsmooth regularizer or constraint: the lasso and ℓ1\ell_1ℓ1​-regularized logistic regression, the graphical lasso for sparse inverse covariance estimation, and constrained least squares, where the nonsmooth…

10 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization+1·Captain: mikedeng1

A New Approach to the Maximum-Flow Problem 1: The Generic Push-Relabel Algorithm and Its Operation BoundResearch Paper

The maximum-flow problem asks how much of a commodity can be sent from a source to a sink through a network whose edges have capacities. It is a basic model in operations research (transportation, scheduling, bipartite matching) and a standard subroutine in combinatorial optimization.

17 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization+1·Captain: mikedeng1

A Supply Chain Theory of Factoring and Reverse Factoring 2: The Retailer's Optimal Reverse Factoring Payment ExtensionResearch Paper

Large retailers pay their suppliers weeks or months after delivery, and small suppliers fill the gap with short-term finance. In factoring the supplier sells the receivable to a factor for immediate cash; in reverse factoring the retailer arranges the program with a bank, which pays the supplier early at a rate priced on the retailer's credit rating.…

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

Are Call Center and Hospital Arrivals Well Modeled by Nonhomogeneous Poisson Processes?: Combining k Equal Subintervals of a Linear Arrival Rate Bounds the Degree of Nonhomogeneity by C/kResearch Paper

Arrival processes to call centers and hospital emergency departments are routinely modeled as nonhomogeneous Poisson processes (NHPPs): Poisson processes whose arrival rate varies over the day. Staffing and queueing models built on this assumption are only as good as the assumption itself, so practitioners test it on data. The standard test, going back to…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: mikedeng1

The Structure of Dynamic Programing Models: A Solution of the Principle of Optimality with Vanishing Tail Is the Optimal ReturnResearch Paper

Dynamic programming, as introduced by Bellman in the early 1950s, solves sequential decision problems through a functional equation: the value of a problem started in a given state equals the best one-stage return plus the value of the problem started in the state that decision leads to. In practice the argument usually runs backwards. One writes down the…

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

Robust Solutions to Uncertain Semidefinite Programs IV: Closed-Form Robust Counterparts under Unstructured PerturbationsResearch Paper

A semidefinite program (SDP) minimizes a linear objective cTxc^TxcTx subject to a linear matrix inequality (LMI) F(x)=F0+∑i=1mxiFi⪰0F(x) = F_0 + \sum_{i=1}^m x_i F_i \succeq 0F(x)=F0​+∑i=1m​xi​Fi​⪰0. In applications the coefficient matrices FiF_iFi​ are measured, estimated or rounded. A solution that is feasible for the nominal data can become infeasible for data that differ from it by an arbitrarily small…

8 thms3 active usersReviewed
🏆Completed
Control TheoryConvex OptimizationOperations Research+1·Captain: mikedeng1

Robust Solutions to Uncertain Semidefinite Programs I: Exact SDP Reformulation of the Robust LMI under Full Linear-Fractional PerturbationsResearch Paper

A semidefinite program (SDP) minimizes a linear objective cTxc^TxcTx subject to a linear matrix inequality (LMI) F(x)=F0+∑i=1mxiFi⪰0F(x) = F_0 + \sum_{i=1}^m x_iF_i \succeq 0F(x)=F0​+∑i=1m​xi​Fi​⪰0. SDPs model problems in control, combinatorial optimization, statistics and engineering design, and they are solved efficiently by interior-point methods. In applications the data F0,…,FmF_0,\dots,F_mF0​,…,Fm​ are rarely…

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

Validation of Subgradient Optimization II: A Unique Optimal Assignment Makes the Dual Optimal Set Full-DimensionalResearch Paper

The subgradient method maximizes a concave, piecewise-linear function w(π)=min⁡k{ck+π⋅vk}w(\pi)=\min_k\{c_k+\pi\cdot v_k\}w(π)=mink​{ck​+π⋅vk​} by moving along a subgradient vkv_kvk​ of an active piece with a prescribed step. Held, Wolfe and Crowder's 1974 paper Validation of subgradient optimization tested the method on three families of Lagrangean duals from combinatorial optimization — the…

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

Lifts of Convex Sets and Cone Factorizations I: A Proper K-Lift of a Convex Body Yields a K-Factorization of Its Slack Operator, and a K-Factorization Yields a K-LiftResearch Paper

Many convex sets that appear in optimization have complicated descriptions in their own space but simple descriptions as projections of higher-dimensional sets. A polytope with exponentially many facets can be the shadow of a polyhedron with polynomially many; the unit disk is the projection of a slice of the cone of 2×22\times 22×2 positive semidefinite…

14 thms3 active usersReviewed
🏆Completed
Control TheoryConvex OptimizationLinear algebra+3·Captain: mikedeng1

Robust Solutions to Least-Squares Problems with Uncertain Data IV: A Semidefinite Upper Bound on the Linear-Fractional Worst-Case Residual, Exact for Full PerturbationsResearch Paper

Least-squares fitting is a standard tool in estimation, identification and data analysis, and its data AAA, bbb are rarely known exactly. El Ghaoui and Lebret (SIAM J. Matrix Anal. Appl. 18(4), 1997) proposed to choose xxx to minimize the worst-case residual over a set of admissible data perturbations. Earlier missions of this series treat unstructured…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraNumerical Analysis+2·Captain: mikedeng1

Robust Solutions to Least-Squares Problems with Uncertain Data I: The Worst-Case Residual and Its Unique MinimizerResearch Paper

The least-squares (LS) problem min⁡x∥Ax−b∥\min_x \|Ax - b\|minx​∥Ax−b∥ assumes that the data A∈Rn×mA \in \mathbb{R}^{n\times m}A∈Rn×m, b∈Rnb \in \mathbb{R}^nb∈Rn are exact. In applications they rarely are: they come from measurements, from linearizations, or from models with neglected dynamics. A classical response is sensitivity analysis or regularization (Tikhonov), where a weight trades the size…

7 thms3 active usersReviewed
PreviousPage 89 of 143Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5259500
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36755492
5NINickrobbins953290156
6VEvebis25800
7FIfizzyinc321735
8SHshivm17520
9KMkmehltretter82998263
10SCShuze Chen9455326

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