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

951–975 of 3527
Open1285Completed3527All4812
🏆Completed
CombinatoricsDiscrete GeometryLinear Optimization·Captain: iris

Combinatorial Optimization (Cook et al.) XIV: Edmonds' Matroid Intersection Polytope TheoremTextbook

Many combinatorial optimization problems ask for a maximum-weight set that is "independent" in two different senses at once: a bipartite matching is a set of edges that uses each left node at most once and each right node at most once; a branching in a digraph is a forest that enters each node at most once. Each of these is a common independent set of two…

27 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation XII: aggregating a stagewise independent multistage program gives a lower bound that refining never decreasesTextbook

A multi-stage stochastic linear program chooses decisions over TTT stages while a random process unfolds, each decision depending only on what has been observed so far. Such problems arise in planning under uncertainty, from production and energy systems to asset-liability management. With a non-discrete distribution the unknowns are functions, and the…

48 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research·Captain: iris

Combinatorial Optimization (Cook et al.) XI: The Subtour Bound Equals the Optimal Held–Karp Bound (corrected: loopless)Textbook

The traveling salesman problem (TSP) asks for a cheapest circuit through every node of a graph with edge costs. No polynomial-time algorithm is known, and exact codes for large instances depend on strong lower bounds to prune their search. Two lower bounds dominate the classical literature. The first is the subtour bound, the optimal value of the linear…

27 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation V: integrated chance constraints with a finite discrete distribution define polyhedraTextbook

A probability constraint in a stochastic linear program asks that a random linear inequality hold with high probability. It counts every violation the same, however large, and the feasible set it defines is in general not convex, as Klein Haneveld's examples show (Klein Haneveld 1986). Integrated chance constraints replace the probability of a shortfall…

17 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOptimization·Captain: iris

Combinatorial Optimization (Cook et al.) VI: The Tutte–Berge Formula for the Maximum Size of a MatchingTextbook

A matching pairs up nodes of a graph along its edges, each node being used at most once. Finding a largest matching is the model problem of combinatorial optimization: the obvious linear relaxation is not integral on non-bipartite graphs, and the methods developed for it (augmenting paths, odd-circuit shrinking, polyhedral descriptions) became standard…

37 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOptimization·Captain: iris

Combinatorial Optimization (Cook et al.) XII: Edmonds' Matroid Polytope TheoremTextbook

The Greedy Algorithm builds a set one element at a time, always adding the heaviest element that keeps the set feasible. For the forests of a graph it finds a maximum-weight forest (Kruskal's algorithm), but for the matchings of a graph it can fail: on a 4-cycle with edge weights 9, 7, 8, 3 it picks the edges of weight 9 and 3 when the edges of weight 7 and…

21 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization·Captain: iris

Combinatorial Optimization (Cook et al.) I: The Characteristic Vector of a Minimum Spanning Tree Is an Optimal Solution of the Spanning-Tree Linear ProgramTextbook

A minimum spanning tree (MST) of a connected graph with edge costs is a cheapest set of edges that connects all nodes and contains no circuit. It is the prototype of a combinatorial optimization problem solved exactly by a greedy rule, and it opens Chapter 2 of Cook, Cunningham, Pulleyblank and Schrijver's Combinatorial Optimization (Wiley, 1998). The…

21 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization·Captain: iris

Combinatorial Optimization (Cook et al.) VII: For Arbitrary Costs the Minimum Cost of a T-Join Equals the Optimal Value of Its Linear ProgramTextbook

A mail carrier must walk every street of a district and return to the post office, and wants to walk as little as possible. Kwan Mei-Ko posed this Chinese postman problem in 1962. Edmonds observed that the extra streets to be walked a second time form a set of edges whose odd-degree nodes are exactly the odd-degree nodes of the street graph, and generalized…

25 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear algebraLinear Optimization·Captain: iris

Combinatorial Optimization (Cook et al.) IX: The Hoffman–Kruskal Theorem: {x≥0:Ax≤b}\{x \ge 0 : Ax \le b\}{x≥0:Ax≤b} Is Integral for All Integral bbb Iff AAA Is Totally UnimodularTextbook

Many combinatorial optimization problems (bipartite matching, maximum flow, shortest paths, transportation and assignment problems) can be written as integer programs

10 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOptimization·Captain: iris

Combinatorial Optimization (Cook et al.) IV: In a Legal Ordering the Last Node's Star Is a Minimum Cut Separating the Last Two NodesTextbook

The global minimum cut problem asks, for a finite undirected graph with nonnegative edge capacities, for a partition of the nodes into two nonempty sides that is crossed by edges of least total capacity. With unit capacities the optimal value is the edge-connectivity of the graph, a basic measure of network reliability; with general capacities the problem…

14 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchStatistics·Captain: iris

Selection of the Most Probable Best: An Allocation Is Optimal for the Relaxed Budget Allocation Problem iff It Satisfies the Global Balance, Pairwise Balance and Zero-Sampling-Ratio ConditionsResearch Paper

Simulation models of service systems, supply chains and financial products depend on input parameters that are themselves estimated from data, such as arrival rates or demand distributions. When a decision maker compares kkk candidate designs by simulation, this input uncertainty means that the best design may differ from one plausible parameter value to the…

18 thms3 active usersReviewed
🏆Completed
Convex OptimizationEconomicsOperations Research·Captain: iris

A Simple Characterization of Supply Correspondences: a supply correspondence is strongly rationalizable iff it is maximal monotone and homogeneous of degree zeroResearch Paper

Producer theory asks which observed supply behaviour is consistent with a profit-maximizing competitive firm. A supply correspondence records, for every vector of prices, the set of production plans the firm is willing to choose. If the firm maximizes profit over a fixed technology, its supply must satisfy testable restrictions; the question of rationalizabi…

15 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: iris

Limit Theory for Taboo-Regenerative Processes: Conditioned on No Exit by Time ttt, the Cycles Around ttt and the Age Converge Uniformly to the Two-Sided Taboo Limit P∗P^*P∗Research Paper

Many stochastic models are studied up to a failure: a queue until overflow, a network until a job is lost, a reliability system until breakdown, a Markov chain until it leaves a set of states. When failure is rare, the informative object is the process conditioned on no failure so far. For Markov chains this is the classical theory of quasi-stationary…

20 thms3 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: iris

Retail Category Management with Slotting Fees: slotting fees raise, lower or keep the retailer's equilibrium product variety on the explicit regions Φ↑, Φ↓ and Φ0Research Paper

A slotting fee is a lump-sum payment a manufacturer makes to a retailer for a place in the retailer's assortment. Such fees are common in grocery retailing, and they are contested: manufacturers and regulators have argued that they limit consumers' access to products and raise barriers to entry (Federal Trade Commission 2003; Bloom, Gundlach and Cannon, Jour…

15 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: iris

Error Analysis of Surrogate Models Constructed through Operations on Sub-models: a product of nnn models exact at x0x_0x0​ has Hessian accuracy of order min⁡{Nig,Nih}\min\{N^g_i,N^h_i\}min{Nig​,Nih​} with constant KFh(x0)K^h_F(x_0)KFh​(x0​)Research Paper

In derivative-free and blackbox optimization, the objective can often be evaluated but not differentiated, and algorithms work with surrogate models built from function values. Their convergence theory depends on how accurate those models are. Conn, Scheinberg and Vicente codified this through fully linear and fully quadratic models; a fully linear class…

17 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: iris

Signaling Service Quality Through Queue Disclosure: with uninformed customers, the unique pure perfect sequential equilibrium pools on concealment below λ^\hat\lambdaλ^, on revelation above itResearch Paper

Whether a service provider should show customers its queue is a classical question in the economics of queues. When customers know the quality of service, the answer is a threshold in market size: Hassin (1986) and Chen and Frank (2004) showed that a revenue-maximizing server conceals the queue when the potential arrival rate is small and reveals it when it…

10 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Joint Estimation and Robustness Optimization: Support functions of estimate uncertainty sets via convex conjugatesResearch Paper

An optimization model often takes an estimated parameter as if it were known exactly. A decision that performs well at that estimate can perform poorly at another parameter value that fits the observations almost as well. Joint estimation and robustness optimization connects these two tasks by constructing the uncertainty set from the estimation procedure…

3 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Adjustable Robust Optimization Reformulations of Two-Stage Worst-Case Regret Minimization Problems: Exact reformulation of absolute regret with objective uncertaintyResearch Paper

A planner who commits resources before learning their eventual returns can evaluate a decision by how much better another decision would have performed after those returns became known. This absolute regret criterion compares against the best feasible hindsight decision under the same realization of uncertainty. It differs from protecting only the lowest…

6 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: Shuze Chen

Distribution-Free Inventory Risk Pooling in a Multilocation Newsvendor: Tight worst-case cost for two locationsResearch Paper

A retailer with stock at several locations can serve a customer from a nearby location when local inventory runs out. This flexibility reduces shortages, but shipping and unused inventory still cost money. Evaluating the benefit requires a joint demand distribution: high demand at one location is easier to absorb when demand elsewhere is low. In practice, a…

8 thms3 active usersReviewed
🏆Completed
Linear OptimizationOptimizationProbability·Captain: Shuze Chen

The Price of Robustness: Tight probability bounds for symmetric uncertaintyResearch Paper

A linear optimization model can prescribe a decision that uses nearly all available capacity. If the coefficients measuring resource consumption are uncertain, even a small change can make that decision infeasible. Protecting against every simultaneous adverse change can instead sacrifice a substantial amount of the nominal objective. Budgeted robustness int…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: Shuze Chen

Supply Chain Inventory Management and the Value of Shared Information: A lower bound on costs under every feasible policyResearch Paper

A supplier receiving orders from several retailers sees only part of the demand that drives the supply chain. Access to the retailers' inventory and demand histories can change when the supplier orders and where it sends available stock. A comparison between two selected policies, however, does not establish how much an unknown better policy could save. A po…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

A Nonparametric Algorithm for Optimal Stopping Based on Robust Optimization: Existence and finite characterization of optimal robust stopping rulesResearch Paper

An exercise decision can depend on today's observed state even when the evolution of that state depends on its history. Examples include deciding when to exercise an option whose reward depends on several asset prices or on earlier observations. A simulator can produce complete trajectories without providing the conditional distributions needed for a…

11 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

ALSO-X and ALSO-X+: Better Convex Approximations for Chance Constrained Programs: ALSO-X is at least as good as CVaRResearch Paper

A chance constrained program chooses a decision before observing uncertainty and limits the probability that its constraints fail. For example, a service system can allow a prescribed fraction of demand realizations to exceed its available capacity. The optimization problem combines a cost objective with a probability requirement. Even when each realized…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Assortment Optimization for a Multistage Choice Model: Revenue-ordered and nested optimal assortmentsResearch Paper

A seller may offer one catalog of products now and a different catalog later. A customer's first purchase can determine which products become available in the second stage. An airline ticket followed by an upgrade offer is one example. When customers anticipate those later offers, changing a continuation assortment can change demand in the first stage as…

10 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: Shuze Chen

Distributionally Robust Markov Decision Processes: S-robust strategies are distributionally optimal and admit a saddle pointResearch Paper

A planner who controls a stochastic system often knows more than a range of possible transition probabilities, but less than a complete probability distribution for those probabilities. For example, a small confidence region may contain a parameter with probability at least 90%, while a larger region contains it with certainty. Optimizing against every…

10 thms3 active usersReviewed
PreviousPage 39 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