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,681 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

Open933Completed2681All3614
🏆Completed
Complexity TheoryDynamic ProgrammingMathematical Logic·Captain: mikedeng1

The Complexity of Markov Decision Processes V: A Quantified Boolean Formula Is True Iff Its Partially Observed Markov Decision Process Has a Zero-Cost PolicyResearch Paper

A Markov decision process is the standard model of sequential decision making under uncertainty: a controller observes the state of a finite system, chooses a decision, pays a cost, and the system moves to a random next state. In many applications (maintenance, inventory with unreliable records, robotics, medical treatment) the controller does not see the…

8 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingGraph TheoryOptimization·Captain: mikedeng1

The Complexity of Markov Decision Processes II: The Optimal Average Cost of a Deterministic Process Is the Least Mean Cost of a Cycle Reachable from the Initial StateResearch Paper

A Markov decision process describes repeated choices whose costs and subsequent states depend on the current state. Such models are used when a decision affects both today's expense and the options available tomorrow. Papadimitriou and Tsitsiklis studied how the computational difficulty of finding an optimal policy changes between stochastic and…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Scheduling Unrelated Parallel Machines 3: On the 3-Dimensional Matching Instances, a Schedule within ρ < 3/2 of Optimal Has Makespan ≤ 2 Iff a Matching ExistsResearch Paper

Minimum makespan scheduling on unrelated parallel machines, written R ∣∣ Cmax⁡R\,||\,C_{\max}R∣∣Cmax​, is one of the basic models of scheduling theory: nnn jobs must each be run on one of mmm machines, and the time a job takes depends arbitrarily on the machine. Lenstra, Shmoys and Tardos (CWI Report OS-R8714, 1987; journal version Math. Programming 46, 1990) gave a polynomial…

8 thms2 active usersReviewed
🏆Completed
Linear OptimizationStatistics·Captain: mikedeng1

Optimal Estimation of Executive Compensation by Linear Programming I: Least Absolute Deviations under Ranking Constraints Equal a Linear ProgramResearch Paper

A firm may know salary bounds and the ranking of positions without having a reliable sample of individual salaries suitable for least-squares estimation. Charnes, Cooper and Ferguson used that kind of partial information to estimate a salary formula from ratings assigned to job factors. Their 1955 paper gives a model in which weights respect the job…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Scheduling Unrelated Parallel Machines 4: With Times in {p, q} and gcd(p, q) = 1, a q-Dimensional Matching Exists Iff a Schedule Has Makespan ≤ pqResearch Paper

Minimum makespan scheduling on unrelated parallel machines asks for an assignment of nnn jobs to mmm machines, where job jjj takes pijp_{ij}pij​ time units on machine iii, so that the largest machine load is as small as possible. In the three-field notation of Graham, Lawler, Lenstra and Rinnooy Kan (1979) it is R ∥ Cmax⁡R\,\|\,C_{\max}R∥Cmax​. It models load balancing across…

7 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryProbability·Captain: mikedeng1

Supply Chain Coordination with Contracts X: Under Forced Compliance, Options Contracts with Shares λ_l and min{λ_h, λ̂_h} Separate the Two Demand Types and Coordinate CapacityTextbook

A manufacturer launching a new product often depends on a single supplier for a critical component, and the supplier must build capacity before demand is known. The manufacturer usually knows more about demand than the supplier does: her sales force, market research and order history give her a forecast the supplier cannot verify, and she has a reason to…

10 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOptimization·Captain: mikedeng1

Supply Chain Coordination with Contracts IX: An Internal Market at the Shadow Price w(α, Q) Allocates Output Optimally, and Paying Its Expectation per Unit Induces the Optimal Effort e°Textbook

In most contracts of the supply chain coordination literature the transfer payments are fixed when the contract is signed: a wholesale price www, a buy-back rate bbb, a revenue share ϕ\phiϕ. Some settings need payments that respond to information arriving after signing, such as realized demand at several retailers and realized production output. Fixing the…

11 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryProbability·Captain: mikedeng1

Supply Chain Coordination with Contracts VIII: In the Two-Location Base-Stock Model the Linear Transfers (39)–(41) Make the Optimal Base Stocks the Unique Nash EquilibriumTextbook

In a supply chain with stock at two locations, a supplier holds inventory that replenishes a retailer, and the retailer serves customers. Each firm sets its own inventory level to minimize its own cost. The retailer bears only part of the cost of customer backorders, and the supplier bears none of the retailer's holding cost, so their incentives differ. The…

10 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOptimization·Captain: mikedeng1

Supply Chain Coordination with Contracts V: With Market-Clearing Prices the Best Wholesale Price Earns θ/(2(1 + θ)) or θ/8, Below the (1 + θ)/8 a Full-Refund Buy-Back AttainsTextbook

A supplier that sells through many competing retailers usually worries that competition among them pushes orders too high, because each retailer ignores the demand it takes from the others. Deneckere, Marvel and Peck (1997) identified the opposite failure. When the retail price is set by the market after demand is realized, retailers who hold too much stock…

11 thms2 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

Supply Chain Coordination with Contracts III: With Effort-Dependent Demand, Buy-Backs, Quantity Flexibility and Revenue Sharing Under-Reward Effort, While a Quantity Discount Gives λΠ(q, e°)Textbook

A supplier selling through a retailer earns more when the retailer works harder at selling. Examples are a better shelf position, more knowledgeable sales staff, local advertising and keeping the display in order. These activities cost the retailer, raise demand, and usually cannot be observed or verified by the supplier, so no contract can be written on…

11 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOptimization+1·Captain: mikedeng1

Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments V: Stackelberg Matroid Pricing Is an Assortment Problem Under a Regular Choice ModelResearch Paper

In Stackelberg network pricing a leader sets prices on some resources, and a follower then buys the cheapest structure available to them, paying the leader for the priced resources they use. The Stackelberg Minimum Spanning Tree problem, introduced by Cardinal, Demaine, Fiorini, Joret, Langerman, Newman and Weimann (Algorithmica 2011), is the version in…

14 thms2 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

A Numerically Stable Dual Method for Solving Strictly Convex Quadratic Programs: The Dual Algorithm Solves the QP or Detects Its Infeasibility in Finitely Many StepsResearch Paper

Strictly convex quadratic programs — minimize a positive definite quadratic subject to linear inequalities — are the subproblems solved at every iteration of successive quadratic programming (SQP) methods for nonlinear optimization, and they arise directly in least-squares estimation with constraints, portfolio selection and model predictive control. In SQP…

9 thms2 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOptimization·Captain: mikedeng1

Finding Minimum-Cost Circulations by Successive Approximation I: The Generic Refine Subroutine Stops Within 3n(n − 1) + 3nm + 3n²(m + n) Update Operations at an ε-Optimal CirculationResearch Paper

Minimum-cost circulation asks how to route flow around a directed network without accumulating flow at any vertex, while minimizing the total cost of the routed units. It is a basic network optimization problem: lower-bound and demand constraints in many flow models can be converted into circulation form. Goldberg and Tarjan's 1987 technical report develops…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsOptimizationTheoretical Computer Science·Captain: mikedeng1

Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments III: The Three Revenue-Ordered Approximation Bounds Are TightResearch Paper

A retailer or an airline chooses which products to offer, and customers choose among what is offered, or buy nothing. Choosing the offer set that maximizes expected revenue is the assortment problem, central to revenue management (Talluri and van Ryzin, 2004). It is NP-hard even for simple mixtures of logit models, so practice relies on heuristics. The most…

15 thms2 active usersReviewed
🏆Completed
OptimizationTheoretical Computer Science·Captain: mikedeng1

Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments II: Revenue-Ordered Assortments Earn OPT/(1 + ln ν), ν the Optimum's Purchase RatioResearch Paper

A retailer that can display only some of its products must choose an assortment: the set of products offered to an arriving customer. Customers substitute: whether a given product is bought depends on what else is on the shelf. The assortment problem asks for the offer set that maximises expected revenue under a model of this substitution behaviour. It is a…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear Optimization·Captain: mikedeng1

Solving Large-Scale Zero-One Linear Programming Problems: A Minimal Cover Inequality Cuts Off x̄ iff the Knapsack Problem (2.12) Has Optimal Value Less Than OneResearch Paper

Large zero–one linear programs can contain constraints involving only a small fraction of their variables. Crowder, Johnson and Padberg study how to extract useful inequalities from one such row while solving the larger program. Their computational method identifies a violated inequality at a current linear programming solution, adds it, and resolves the…

8 thms2 active usersReviewed
🏆Completed
Optimal TransportOptimizationProbability·Captain: mikedeng1

Quantifying Distributional Model Risk via Optimal Transport 3: A Worst-Case Transport Plan Exists in a Locally Compact Normed Space under Growth Conditions on c and fResearch Paper

In distributionally robust modelling, a baseline probability model μ\muμ on a space SSS is distrusted, and the analyst reports the largest expected loss over every model within a budget of μ\muμ. Blanchet and Murthy (arXiv:1604.01446; Math. Oper. Res. 44(2), 2019, doi:10.1287/moor.2018.0936) measure the budget with an optimal transport cost and prove strong…

20 thms2 active usersReviewed
🏆Completed
Optimal TransportOptimizationProbability·Captain: mikedeng1

Quantifying Distributional Model Risk via Optimal Transport 2: The Worst-Case Probability of a Closed Set A Equals the Baseline Probability of Its Inflation {x : c(x, A) ≤ 1/λ*}Research Paper

A probability model μ\muμ for a risk quantity, such as the reserve process of an insurer or the path of a queue, is usually chosen for tractability or fitted to limited data, and the true law of the system is unknown. Distributional model risk asks how large a probability of interest could be if the true law were any model "close" to μ\muμ. When closeness is…

17 thms2 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

Scheduling Deteriorating Jobs on a Single Processor I: Under Linear Deterioration, Sequencing by Increasing E(X_i)/α_i Minimizes the Expected MakespanResearch Paper

In classical single-machine stochastic scheduling, NNN jobs with independent random processing requirements XiX_iXi​ are processed one after another, and the makespan (the completion time of the last job) is the same for every schedule that never idles: it is X1+⋯+XNX_1+\dots+X_NX1​+⋯+XN​. Research therefore concentrated on weighted flow times and rewards. Browne and Yechiali (Ope…

6 thms2 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers I: Under a Lagrangian Saddle Point, ADMM Residuals Vanish and Objective Values ConvergeTextbook

The alternating direction method of multipliers (ADMM) is one of the most widely used algorithms for large-scale convex optimization in statistics, machine learning and signal processing. Its appeal is decomposition: a problem whose objective splits into two parts, coupled only by a linear constraint, is solved by alternately minimizing over each part and…

13 thms2 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems 4: For Symmetric Cost and Right-Hand-Side Uncertainty, the Adaptability Gap Is at Most FourResearch Paper

Two-stage optimization separates a decision made before uncertainty is observed from one made after a scenario is known. A fully adaptive policy can choose a different second-stage decision in each scenario, while a static robust solution commits to a single second-stage decision that works in every scenario. Static solutions can be simpler to implement,…

9 thms2 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOptimization·Captain: mikedeng1

Projected Newton Methods for Optimization Problems with Simple Constraints: The Projected Newton Method Converges Superlinearly to the Minimum of a Convex Function over the Nonnegative OrthantResearch Paper

Smooth optimization with nonnegative variables appears when the variables are Lagrange multipliers for inequality constraints or when an objective incorporates an augmented Lagrangian or an exact penalty. Bertsekas studies how to retain a Newton-like convergence rate in this setting while using an iteration that projects a scaled gradient step onto the…

9 thms2 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems 2: On the Non-Symmetric Uniform Simplex, the Robust Optimum Is at Least n + 1 Times the Stochastic OneResearch Paper

Many operations problems are decided in two stages: a first-stage decision is fixed before an uncertain quantity is revealed, and a second-stage (recourse) decision is chosen afterwards. Two classical ways to optimize such a problem differ in how they treat the uncertainty. Two-stage stochastic optimization minimizes the expected cost under a probability…

11 thms2 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems 2: Worst-Case Distribution with Largest Covariance for Piecewise-Linear PortfoliosResearch Paper

A portfolio manager who maximizes expected utility needs the distribution of asset returns, but in practice only estimates of its first two moments are available, and these estimates are themselves noisy. Distributionally robust optimization handles this by optimizing against the worst distribution in a set of plausible ones. Delage and Ye (Operations…

9 thms2 active usersReviewed
🏆Completed
Linear OptimizationOptimizationTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines That Run at Different Speeds: A min{K + 2√K + 1, 1.89 log m + O(√log m)}-Approximation for Q|prec|CmaxResearch Paper

Graham (1966) showed that list scheduling finds a schedule within a factor 222 of optimal for precedence-constrained jobs on identical parallel machines, the first performance guarantee for an approximation algorithm. When the machines run at different speeds (uniformly related machines), the same analysis breaks down, and for two decades the problem …

16 thms2 active usersReviewed
PreviousPage 96 of 108Next

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