Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Operations Research

3,614 missions · 2,642 completed

The discipline of applying mathematical analysis to complex decision problems in operations: allocating scarce resources, scheduling, routing, inventory, and the design of service and production systems. Drawing on mathematical programming, stochastic modeling, queueing, simulation, and game-theoretic reasoning, it seeks policies that perform provably well in systems shaped by constraints, congestion, and uncertainty.

Missions

Open972Completed2642All3614
🏆Completed
ProbabilityStochastic Systems·Captain: Shuze Chen

Processing Networks IX: Fluid Stability of the Proportionally Fair AllocationTextbook

Every control policy formalized so far in this series — HLSPS (mission VI), back-pressure/ max-weight (mission VIII) — allocates service effort to entire job classes as indivisible units. Proportional fairness takes a different starting point: it is a general-purpose recipe for dividing a shared, continuously divisible resource among competing demands,…

12 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryLinear Optimization·Captain: mikedeng1

The Assignment Game I: The Core 1: The Core Is the Set of Optimal Solutions of the Dual Assignment LPResearch Paper

A two-sided market in which each participant trades with at most one partner on the other side — houses and buyers, workers and firms, producers and consumers under exclusive bilateral contracts — is the setting of L. S. Shapley and M. Shubik's assignment game (Int. J. Game Theory 1 (1971) 111–130). Money is transferable, so the natural solution concept is…

6 thms3 active usersReviewed
🏆Completed
ProbabilityStochastic Systems·Captain: Shuze Chen

Processing Networks V: Lyapunov Stability Criteria for Fluid ModelsTextbook

Mission III's Theorem 6.2 reduces SPN stability to a question about deterministic fluid model solutions: does every solution of a fixed system of equations get driven to the origin, uniformly in its starting size? Mission IV showed how to derive the extra, policy-specific equations a fluid model must satisfy. What remains is a method for proving that a…

15 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingProbability·Captain: mikedeng1

On the Optimality of Generalized (s, S) Policies: A Generalized (s, S) Policy Is Optimal in Every Period of the Finite-Horizon Inventory ProblemResearch Paper

In a periodic-review inventory system a manager observes the stock level before ordering, decides how much to order, and then faces random demand. When ordering costs a fixed setup charge plus a constant price per unit, Scarf (1960) proved that an (s,S)(s,S)(s,S) policy is optimal in every period of a finite-horizon problem: order up to SSS when the stock falls below sss,…

17 thms3 active users
🏆Completed
Convex OptimizationFunctional AnalysisOptimization·Captain: mikedeng1

A Dynamical Approach to an Inertial Forward-Backward Algorithm for Convex Minimization: The IFB Iterates Minimize the Objective and Converge Weakly to a MinimizerResearch Paper

Many problems in signal processing, statistics and operations research ask to minimize a sum Θ=Φ+Ψ\Theta = \Phi + \PsiΘ=Φ+Ψ of a nonsmooth convex term Φ\PhiΦ (a constraint indicator, an ℓ1\ell^1ℓ1 penalty) and a smooth term Ψ\PsiΨ. The standard method is the forward-backward (proximal-gradient) algorithm: an explicit gradient step on Ψ\PsiΨ followed by a proximal step on Φ\PhiΦ.…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Dual Stochastic Dominance and Related Mean-Risk Models 1: Second-Degree Stochastic Dominance Is Dominance of Absolute Lorenz CurvesResearch Paper

Comparing uncertain outcomes is the basic problem of decision making under risk. Second-degree stochastic dominance (SSD) is the comparison that every risk-averse decision maker who prefers larger outcomes agrees with: XXX dominates YYY in this sense exactly when E U(X)≥E U(Y)\mathbb E\,U(X)\ge\mathbb E\,U(Y)EU(X)≥EU(Y) for every nondecreasing concave utility UUU for which the…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryGroup Theory+1·Captain: mikedeng1

λ1, Isoperimetric Inequalities for Graphs, and Superconcentrators 2: Cayley Graphs of Finite Quotients of a Property (T) Group Are Linear EnlargersResearch Paper

An expander is a sparse graph in which every set of vertices has many neighbours outside itself. Expanders are the building blocks of superconcentrators (sparse directed graphs that route any rrr inputs to any rrr outputs along vertex-disjoint paths), of sorting and switching networks, and of many constructions in complexity theory and coding; the survey of…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Robust Control of Markov Decision Processes with Uncertain Transition Matrices 4: The Dual of the Worst-Case Expectation over a Kullback-Leibler BallResearch Paper

A robust Markov decision process replaces the unknown transition probabilities of an MDP by sets of plausible values and optimises against the worst case. Nilim and El Ghaoui (Oper. Res. 53 (2005)) showed that, when the uncertainty is rectangular (each row of each transition matrix varies independently in its own set), the robust problem is solved by a…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

λ1, Isoperimetric Inequalities for Graphs, and Superconcentrators 1: A Diameter Bound from λ1Research Paper

The eigenvalues of the Laplacian of a graph carry metric information about the graph. The second-smallest one, λ1(G)\lambda_1(G)λ1​(G), was named the algebraic connectivity by Fiedler (Fiedler 1973), who showed it is positive exactly for connected graphs. N. Alon and V. D. Milman (J. Combin. Theory Ser. B 38 (1985) 73–88) showed that a large λ1\lambda_1λ1​ also forces two…

9 thms3 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingOptimization·Captain: mikedeng1

Robust Control of Markov Decision Processes with Uncertain Transition Matrices 3: Stationary Policies Suffice and the Stationary/Time-Varying Uncertainty Gap Vanishes GeometricallyResearch Paper

A Markov decision process (MDP) is controlled with transition probabilities estimated from data, and optimal policies computed for the estimated model can perform badly when the estimates are off. Robust MDPs replace the single transition model by a set of models and optimize the worst case over that set. Two readings of "the set" are possible. In the statio…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: mikedeng1

A Linear-Time Algorithm for Finding a Sparse k-Connected Spanning Subgraph of a k-Connected Graph 2: FOREST's Forests E_i Preserve Local Node-Connectivity up to i in a Simple GraphResearch Paper

Given a kkk-connected graph, many connectivity algorithms run in time that grows with the number of edges ∣E∣|E|∣E∣. A sparse certificate is a spanning subgraph with only O(k∣V∣)O(k|V|)O(k∣V∣) edges that is still kkk-connected; computing one first and running the expensive algorithm on it replaces ∣E∣|E|∣E∣ by k∣V∣k|V|k∣V∣ in the bound. Finding a kkk-connected spanning subgraph with the minimum…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: mikedeng1

A Linear-Time Algorithm for Finding a Sparse k-Connected Spanning Subgraph of a k-Connected Graph 1: The FOREST Decomposition Preserves Local Edge-ConnectivityResearch Paper

Many graph algorithms for connectivity questions run in time proportional to the number of edges. When the question is only whether a graph is kkk-edge-connected, or what its local edge-connectivities are up to a threshold kkk, most edges are irrelevant: a spanning subgraph with O(k∣V∣)O(k|V|)O(k∣V∣) edges already carries the answer. Such a subgraph is called a sparse…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOptimization·Captain: Shuze Chen

Disjunctive Programming VI: Extended Formulations for Perfectly Matchable Subgraph PolytopesTextbook

Many polytopes that arise from combinatorial optimization problems have no small facet description in their natural variable space, yet become describable by a compact linear system once lifted to a higher-dimensional space of auxiliary variables and projected back down — Chapter 2's own extended formulation of the convex hull of a disjunctive set is one…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization·Captain: mikedeng1

Cones of Matrices and Set-Functions and 0–1 Optimization III: The Defect of a Stable Set Inequality Bounds Its N-IndexResearch Paper

Many 0–1 optimization problems can be written as linear programs over the convex hull of the 0–1 points of a polytope, but that hull usually has no manageable description by inequalities. Lift-and-project methods approximate it by a sequence of convex sets. Each set comes from a linear or semidefinite system in more variables, followed by a projection.…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOptimization·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 TheoryTheoretical 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+1·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
CombinatoricsOptimizationTheoretical Computer Science·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
Markov ChainStochastic 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
CombinatoricsOptimization·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
CombinatoricsOptimization·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
Optimal 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 AnalysisOptimization·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
Graph TheoryOptimizationTheoretical Computer Science·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
Graph TheoryOptimizationTheoretical Computer Science·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
PreviousPage 64 of 106Next

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