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.

3558 completed missions

Missions

2101–2125 of 3558
Open1254Completed3558All4812
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Introduction to the Scenario Approach V: Support Sets Certify the Violation of Nonconvex Scenario SolutionsTextbook

The scenario approach replaces an optimization problem with uncertain constraints θ∈Θδ\theta\in\Theta_\deltaθ∈Θδ​, δ∈Δ\delta\in\Deltaδ∈Δ, by the program that enforces only NNN constraints Θδ1,…,ΘδN\Theta_{\delta_1},\dots,\Theta_{\delta_N}Θδ1​​,…,ΘδN​​ drawn at random from the distribution P\mathbb PP of the uncertainty. Its solution θ∗\theta^*θ∗ is then judged by its violation, the probability that a…

7 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue: The Competitive Ratio of the Primal-Dual Allocation AlgorithmResearch Paper

Search engines sell advertisement slots next to their results through ad-auctions. Advertisers bid on keywords, and each advertiser also sets a daily budget: the most it is willing to pay in a day. Queries arrive one at a time and each must be assigned to an advertiser at once, with no knowledge of the queries still to come. The seller's revenue from an…

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

Value of Information in Bayesian Routing Games I: Sign and Monotonicity of the Relative Value of Information Across Size RegimesResearch Paper

Traffic information systems (TIS) such as navigation apps send drivers noisy signals about the state of a road network: incidents, weather, closures. When several such systems coexist, each with its own subscriber base and its own information, a natural question for operators and regulators is whether subscribing to one system rather than another actually…

15 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research+1·Captain: mikedeng1

Computing Optimal (s, S) Inventory Policies III: Selecting an (s, S) Policy That Is Optimal for Every Starting StockResearch Paper

The periodic-review inventory model with a fixed ordering cost is one of the basic models of operations research. When every order incurs a set-up cost KKK in addition to holding and shortage costs, the optimal replenishment rule over an infinite horizon is, under standard convexity assumptions, a stationary (s,S)(s, S)(s,S) policy: whenever the stock falls below the…

6 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchStochastic Systems·Captain: mikedeng1

Computing Optimal (s, S) Inventory Policies II: Bounds on the Optimal s and S of the n-Period Model from the One-Period CostResearch Paper

The (s,S)(s, S)(s,S) policy is the standard ordering rule for a single stocked item with a fixed charge per order: when the stock position falls below a reorder point sss, order up to a level SSS; otherwise order nothing. Scarf (1960) proved that when the expected one-period cost is convex, some (s,S)(s, S)(s,S) policy is optimal in every period of a finite-horizon model with…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsDiscrete GeometryOperations Research·Captain: mikedeng1

Extremal Problems in Discrete Geometry: The Szemerédi–Trotter Incidence BoundResearch Paper

How many times can nnn points and ttt lines in the plane meet? The question is the prototype of incidence geometry, and the answer controls a long list of problems in discrete and computational geometry: the number of lines rich in points, the number of distinct distances or unit distances among nnn points, the complexity of arrangements, and sum–product…

8 thms3 active usersReviewed
🏆Completed
Dynamical SystemsTopology·Captain: mikedeng1

Ordinary Differential Equations and Dynamical Systems XI: The Smale HorseshoeTextbook

The Smale horseshoe is the standard example of a smooth invertible map of the plane with chaotic dynamics. Smale introduced it in the 1960s as the mechanism behind the complicated orbits near a transverse homoclinic point, and it became the basic model of hyperbolic invariant sets (Smale 1967). Its importance for differential equations is the Smale–Birkhoff…

20 thms3 active usersReviewed
🏆Completed
AnalysisDynamical Systems·Captain: mikedeng1

Ordinary Differential Equations and Dynamical Systems X: Periodic Orbits and the Poincaré MapTextbook

Periodic solutions are the simplest non-stationary long-time behaviour of an autonomous system x˙=f(x)\dot x = f(x)x˙=f(x): limit cycles in oscillators and population models, closed orbits of conservative systems. The first question about a periodic orbit is whether it is stable. Poincaré introduced the first-return map on a transversal section, which turns this question…

22 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Algorithmic Mechanism Design VI: With Verification, the Compensation-and-Bonus Mechanism Is a Strongly Truthful Optimal ImplementationResearch Paper

Scheduling tasks on machines owned by self-interested parties is the running example of Nisan and Ronen's Algorithmic Mechanism Design (Games and Economic Behavior 35, 2001), the paper that introduced the study of mechanisms whose allocation rule is an algorithm with a computational objective. Each machine (agent) privately knows how long it needs for each…

8 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+2·Captain: mikedeng1

Algorithmic Mechanism Design V: The Randomly Biased Min Work Mechanism Is a Strongly Truthful 7/4-Approximation for Two AgentsResearch Paper

Algorithmic mechanism design, introduced by Nisan and Ronen (Games Econ. Behav. 35, 2001), studies optimization problems whose input is held by self-interested agents. Each agent reports its private data to a protocol, and the protocol must choose an output and payments so that reporting the truth is in every agent's interest while the chosen output is…

10 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Algorithmic Mechanism Design IV: No Local Truthful Mechanism Achieves a c-Approximation for Task Scheduling for Any c < nResearch Paper

Nisan and Ronen's Algorithmic Mechanism Design (Games and Economic Behavior 35, 2001) asks how well a computational task can be carried out when its inputs are held by self-interested agents who may lie about them. Their test case is scheduling on unrelated machines: tasks must be assigned to agents (machines), each agent privately knows how long it needs…

8 thms3 active usersReviewed
🏆Completed
AnalysisDynamical Systems·Captain: mikedeng1

Ordinary Differential Equations and Dynamical Systems IX: Interval Maps, Symbolic Dynamics and the Tent-Map RepellorTextbook

One-dimensional maps are the smallest systems in which deterministic dynamics becomes unpredictable. Chapter 11 of Gerald Teschl's graduate text Ordinary Differential Equations and Dynamical Systems (author's version; AMS Graduate Studies in Mathematics 140, 2012, doi:10.1090/gsm/140) uses them to make the word "chaos" precise. The chapter proves that a…

21 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Algorithmic Mechanism Design II: A Lower Bound for Truthful Task SchedulingResearch Paper

Algorithms deployed on the Internet often take their inputs from parties who own them and who may lie when lying pays. Nisan and Ronen's Algorithmic Mechanism Design (Games and Economic Behavior 35, 2001) proposed studying optimization problems in this setting: the algorithm designer may hand out payments, and must guarantee that the intended output is…

11 thms3 active usersReviewed
🏆Completed
AnalysisDynamical Systems·Captain: mikedeng1

Ordinary Differential Equations and Dynamical Systems VI: The Poincaré–Bendixson TheoremTextbook

Long-time behaviour is the central question about an autonomous differential equation x˙=f(x)\dot x = f(x)x˙=f(x): where does a trajectory go as t→±∞t \to \pm\inftyt→±∞? In the plane this question has an almost complete answer. The theory begun by Poincaré (Mémoire sur les courbes définies par une équation différentielle, 1881–1886) and completed by Bendixson (Sur les courbes…

16 thms3 active usersReviewed
🏆Completed
AnalysisControl TheoryDynamical Systems·Captain: mikedeng1

Ordinary Differential Equations and Dynamical Systems V: Limit Sets and the Krasovskii–LaSalle PrincipleTextbook

Most differential equations that model physical, biological or engineered systems cannot be solved in closed form, yet the question asked about them is usually qualitative: does the system settle down to an equilibrium, and does it stay near the equilibrium when perturbed? Liapunov's direct method answers that question without solving the equation, by…

19 thms3 active usersReviewed
🏆Completed
AnalysisDynamical Systems·Captain: mikedeng1

Ordinary Differential Equations and Dynamical Systems I: Existence, Uniqueness and Peano's TheoremTextbook

Almost every quantitative statement about an ordinary differential equation, from the stability of an equilibrium to the existence of a periodic orbit, presupposes that the equation has a solution through each initial point and, usually, that this solution is unique and depends continuously on the data. Chapter 2 of Gerald Teschl's graduate textbook Ordinary…

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

Single Machine Scheduling with Release Dates III: The Random Per-Job α-Schedule with a Truncated Exponential DensityResearch Paper

Scheduling jobs with release dates on one machine to minimize the total weighted completion time, written 1∣rj∣∑wjCj1|r_j|\sum w_jC_j1∣rj​∣∑wj​Cj​, is strongly NP-hard even with unit weights (Lenstra, Rinnooy Kan & Brucker, 1977). It is a basic model of scheduling theory and a standard testbed for approximation algorithms built on linear programming relaxations. Several LP…

21 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

Single Machine Scheduling with Release Dates II: The Random α-Schedule with a Truncated Exponential DensityResearch Paper

Minimizing the total weighted completion time ∑jwjCj\sum_j w_j C_j∑j​wj​Cj​ of jobs with release dates on a single machine, written 1 ∣ rj ∣ ∑wjCj1\,|\,r_j\,|\,\sum w_j C_j1∣rj​∣∑wj​Cj​ in scheduling notation, is strongly NP-hard. It is one of the basic models of machine scheduling, and it has served as a test case for a general technique in approximation algorithms: solve a linear programming…

18 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryDynamical SystemsProbability+1·Captain: mikedeng1

On the Global Convergence of Stochastic Fictitious Play II: Almost Sure Convergence in Zero-Sum Games and Symmetric Games with an Interior ESSResearch Paper

Fictitious play is the oldest model of learning in games: players repeatedly play a fixed normal form game, and each round every player best-responds to the empirical frequencies of the opponents' past play. Brown (1951) proposed it as an algorithm for computing the value of a zero-sum game, and Robinson (1951) proved that the empirical frequencies converge…

12 thms3 active usersReviewed
🏆Completed
AnalysisPartial Differential EquationsPure Mathematics·Captain: mikedeng1

Tasty Bits of Several Complex Variables VI: The Hartogs PhenomenonTextbook

In one complex variable every open set is the natural domain of some holomorphic function: 1/z1/z1/z on a punctured disc cannot be continued across the puncture. In two or more variables this fails in a striking way. Hartogs observed in 1906 that a function holomorphic on the complement of a compact set inside a domain always extends across the hole (Hartogs,…

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

On the Global Convergence of Stochastic Fictitious Play I: Every Additive Random Utility Choice Function Has an Admissible Deterministic Perturbation RepresentationResearch Paper

Models of learning in games, and discrete choice models in econometrics, describe an agent who does not always pick the best alternative. Two descriptions of such an agent are standard. In the additive random utility model (McFadden 1981; Anderson, de Palma and Thisse 1992) the agent maximizes payoffs perturbed by random shocks. In the deterministic…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsDiscrete GeometryOperations Research+1·Captain: Shuze Chen

Discrete Convex Analysis XIV: The König-Egerváry Theorem for Mixed MatricesTextbook

Every physical or engineering model built from linear relations mixes two kinds of numbers. Some coefficients are exact — the ±1\pm 1±1 entries recording Kirchhoff's current and voltage laws in an electrical network, or the incidence structure of a mechanical linkage — because they come from a topological or combinatorial fact, not a measurement. Others are…

16 thms3 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research+1·Captain: Shuze Chen

Discrete Convex Analysis XXXV: Gross Substitutes and Equilibrium PricesTextbook

This mission continues chapter 11's account of the M♮-concave/M♮-convex exchange-economy model begun in mission 14-economic-equilibrium, placing seven of that chunk's own results that were previously left out-of-cone: the two gross-substitutes-style characterizations of M♮-concavity (§11.3), the transfer theorem that lifts an equilibrium of the continuous…

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

The Distributionally Robust Chance-Constrained Vehicle Routing Problem V: Worst-Case Value-at-Risk over Covariance Ambiguity Sets as a Quadratically Constrained ProgramResearch Paper

In the capacitated vehicle routing problem (CVRP) a fleet of mmm vehicles of capacity QQQ leaves a depot and serves nnn customers; every customer is visited once, and the load of each route must not exceed QQQ. In practice customer demands are uncertain at planning time. The chance-constrained CVRP asks that each route respect the capacity with probability at least …

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

The Distributionally Robust Chance-Constrained Vehicle Routing Problem IV: Worst-Case Value-at-Risk over First-Order Generic Moment Ambiguity Sets as a Convex ProgramResearch Paper

In the capacitated vehicle routing problem (CVRP) a depot serves customers VC={1,…,n}V_C=\{1,\dots,n\}VC​={1,…,n} with mmm vehicles of capacity QQQ, and every route must respect the capacity. When customer demands are uncertain, the distributionally robust chance-constrained CVRP of Ghosal and Wiesemann (Oper. Res. 68(3), 2020) requires every route to meet its capacity with…

8 thms3 active usersReviewed
PreviousPage 85 of 143Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5240500
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36735482
5NINickrobbins953289156
6VEvebis25800
7FIfizzyinc321725
8SHshivm17510
9KMkmehltretter82972263
10SCShuze Chen9455324

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