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
EconomicsOptimization·Captain: mikedeng1

Advance Selling and Upgrading in Priority Queues: With Only Online Customers, Upgrading Raises the Optimal Revenue Exactly When Bₛ − Bₐ > α(p(λₕ) − p(λₗ))Research Paper

Amusement parks and similar attractions sell two kinds of ticket for the same ride: a regular ticket, which joins a first-come-first-served queue, and a fast-track ticket, which joins a separate queue served with non-preemptive priority. Increasingly these tickets are sold online in advance, before the customer knows whether the park will be crowded on the…

9 thms4 active usersReviewed
🏆Completed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

A Soft Robust Model for Optimization Under Ambiguity: For Every δ > 0, Soft Robust Feasibility Is a Convex Risk Measure Constraint, and Every Normalized Convex Risk Measure Arises This WayResearch Paper

Optimization under uncertainty usually fixes one probability distribution P\mathbb PP for the uncertain data and optimizes an expected payoff, or fixes a set Q\mathcal QQ of distributions and protects against the worst one (robust optimization). The first is sensitive to a misspecified P\mathbb PP; the second can be very conservative, because it treats a barely…

10 thms4 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Stochastic Dual Dynamic Integer Programming 3: The Convex Lower Envelope of a Function on {0,1}^n Is Piecewise Linear and Agrees with It at Every Binary PointResearch Paper

Multistage stochastic integer programs model sequential decisions under uncertainty in which some decisions are discrete: unit commitment in power systems, capacity expansion, production planning with setups. The standard decomposition methods for multistage stochastic linear programs, nested Benders decomposition and stochastic dual dynamic programming…

9 thms4 active usersReviewed
🏆Completed
Convex OptimizationDynamic ProgrammingOptimization·Captain: mikedeng1

On the Convergence of Decomposition Methods for Multistage Stochastic Convex Programs 1: Deterministic Cutting-Plane Bellman Approximations Become Exact Along the Generated TrajectoriesResearch Paper

Multistage stochastic programs model sequential decisions under uncertainty: hydro-thermal scheduling, inventory and capacity planning, portfolio management. The dominant solution methods, Stochastic Dual Dynamic Programming (SDDP, Pereira and Pinto 1991) and its relatives CUPPS and DOASA, never compute the Bellman (future-cost) functions of the problem.…

12 thms4 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

On the tightness of SDP relaxations of QCQPs 3: Quadratic Eigenvalue Multiplicity k ≥ m + 2 Gives conv(D) = D_SDP Without PolyhedralityResearch Paper

A quadratically constrained quadratic program (QCQP) minimizes a quadratic function subject to quadratic inequality and equality constraints. The class contains nonconvex problems such as binary programs, max-cut, the trust-region subproblem and many problems in signal processing and control. A standard convex approximation is the Shor semidefinite…

11 thms4 active usersReviewed
🏆Completed
Linear OptimizationProbabilityTheoretical Computer Science·Captain: mikedeng1

Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios II: In the Deterministic Case Multi-price Ranking Is minᵢ F(𝒫ᵢ)-CompetitiveResearch Paper

Online matching models a platform that must commit resources to requests as they arrive, without knowing the future. In revenue management the resources are items in limited supply and the requests are customers, and the firm also chooses the price. Ma and Simchi-Levi (arXiv:1905.04770, Oper. Res. 2020, DOI 10.1287/opre.2019.1957) give algorithms whose…

9 thms4 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

Multistage Distributionally Robust Mixed-Integer Programming with Decision-Dependent Moment-Based Ambiguity Sets I: Under Moment Bounds, the Stage Bellman Equation Is One LP-Dual MinimizationResearch Paper

In many planning problems the decision changes the uncertainty it faces. Opening a facility raises the demand observed near it; a maintenance decision changes the failure distribution of a component; a price shifts the demand law. Decision-dependent uncertainty of this kind breaks the standard assumption of stochastic programming that the probability…

7 thms4 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

Multistage Distributionally Robust Mixed-Integer Programming with Decision-Dependent Moment-Based Ambiguity Sets II: Under Mean and Covariance, the Stage Bellman Equation Is One LP-Dual MinimizationResearch Paper

Many planning problems are solved in stages. A decision is taken, uncertainty is revealed, and the next decision reacts to it. Facility location, capacity expansion and network design all fit this pattern. In a growing class of such problems, the distribution of the uncertainty depends on the decision: opening a facility changes the demand it attracts, and…

6 thms4 active usersReviewed
🏆Completed
CombinatoricsOptimizationTheoretical Computer Science·Captain: mikedeng1

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature I: Swap-Local Optima of the Non-Oblivious Potential Are (1 − c/e)-Approximate for Submodular MaximizationResearch Paper

Maximizing a monotone submodular function over the bases of a matroid is the standard model for coverage, facility location, sensor placement and welfare maximization. The best possible approximation factor in the value-oracle model is 1−1/e1 - 1/e1−1/e (Nemhauser–Wolsey 1978; Călinescu–Chekuri–Pál–Vondrák 2011). Many functions met in practice are far from the worst…

9 thms4 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

K-Adaptability in Two-Stage Robust Binary Programming 2: The K-Adaptability Problem with Objective Uncertainty Is Equivalent to the MILP (5)Research Paper

Many planning problems are decided in two stages. A here-and-now decision xxx is taken before an uncertain parameter vector ξ\xiξ is observed, and a wait-and-see decision yyy is taken afterwards. When the wait-and-see decision is binary (which route to drive, which facility to open, which machine to schedule), the resulting two-stage robust binary program has no…

11 thms4 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

K-Adaptability in Two-Stage Robust Binary Programming 3: Under Constraint Uncertainty, Every K < |𝒴| Can Leave a Strict GapResearch Paper

Two-stage robust optimization models decisions taken in two steps around an uncertain parameter ξ\xiξ: a here-and-now decision xxx is fixed before ξ\xiξ is revealed, and a wait-and-see (recourse) decision yyy is chosen afterwards, against the worst case of ξ\xiξ in an uncertainty set Ξ\XiΞ. When the recourse is binary — routing, scheduling, facility opening, emergency…

7 thms4 active usersReviewed
🏆Completed
Optimal TransportOptimizationProbability·Captain: mikedeng1

A Short and General Duality Proof for Wasserstein Distributionally Robust Optimization IV: On a Polish Space, the Maximum-Transport-Cost Worst-Case Loss Equals E[sup{f(x) : c(X̂, x) ≤ ρ}]Research Paper

In Wasserstein distributionally robust optimization (DRO) a decision is evaluated against the worst distribution within an optimal-transport ball around a nominal distribution P^\widehat{\mathbb P}P. For a Wasserstein distance of finite order ppp, the ball constrains an average transport cost. The case p=∞p=\inftyp=∞ is different. The ∞\infty∞-Wasserstein distance …

16 thms4 active usersReviewed
🏆Completed
Optimal TransportOptimizationProbability·Captain: mikedeng1

Residuals-based distributionally robust optimization with covariate information 1: Wasserstein ER-DRO with the Enlarged Radius (10) Certifies Its Out-of-Sample Cost with Probability 1−αResearch Paper

Many operational decisions are made after observing covariates that carry information about the uncertainty: a retailer sets inventory after seeing weather and calendar features that predict demand, a grid operator commits generation after seeing a load forecast. The decision problem is a conditional stochastic program: choose z∈Zz\in\mathcal Zz∈Z to minimize …

15 thms4 active usersReviewed
🏆Completed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Distributionally Robust Joint Chance Constraints with Second-Order Moment Information I: Worst-Case CVaR Is Exact for Individual Chance Constraints with Concave or Quadratic LossesResearch Paper

A chance constraint asks that an uncertain constraint hold with high probability: a decision is acceptable if the loss L(ξ~)L(\tilde\xi)L(ξ~​) it incurs is nonpositive with probability at least 1−ϵ1-\epsilon1−ϵ. Chance constraints appear in portfolio selection, power-system dispatch, inventory control and engineering design, wherever an occasional violation is tolerable but…

18 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationMachine Learning·Captain: mikedeng1

Fast Convergence of Regularized Learning in Games I: If Every Player Runs Optimistic FTRL with Step Size 1/(2(n−1)), the Sum of All Players' Regrets Is at Most 2n(n−1)RResearch Paper

When the players of a game repeatedly adjust their strategies with no-regret learning algorithms, the empirical distribution of play converges to a coarse correlated equilibrium, and in smooth games the average social welfare approaches the price-of-anarchy guarantee of the game (Roughgarden 2009). For generic no-regret algorithms such as Hedge the…

9 thms4 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: mikedeng1

Intrinsic Robustness of the Price of Anarchy I: Every Coarse Correlated Equilibrium of a Smooth Game Has Expected Cost at Most the Robust Price of Anarchy Times OptimalResearch Paper

The price of anarchy (POA) of a game measures how much selfish behaviour costs: it is the ratio between the largest cost of an equilibrium and the cost of an optimal outcome, for a nonnegative objective such as the sum of the players' costs. Since Koutsoupias and Papadimitriou (1999) and Roughgarden and Tardos (2002), POA bounds have been proved for…

12 thms4 active users
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

A Modern Introduction to Online Learning IX: Cover's Universal Portfolio with Uniform or Dirichlet(1/2) Prior Has Logarithmic Regret Against Constantly Rebalanced PortfoliosTextbook

A portfolio manager chooses fractions of current wealth to place in several stocks before seeing that day’s market gains. The gains need not follow a statistical model: a sequence may be selected adversarially, with some stocks losing all value on a given day. A useful benchmark is the best constantly rebalanced portfolio, which holds the same fractions…

9 thms4 active usersReviewed
🏆Completed
OptimizationTheoretical Computer Science·Captain: mikedeng1

Joint Assortment Optimization and Customization under a Mixture of Multinomial Logit Models 1: Augmented Greedy Earns a (1 − 1/e) Fraction of the Optimal Revenue from the Complete Customer TypesResearch Paper

Retailers that carry a limited range of products often know something about a customer before choosing which of those products to display. The customized assortment problem asks which products to carry when the displayed assortment may be tailored to the arriving customer's type. This separates the first-stage capacity decision from the later offer…

9 thms4 active usersReviewed
🏆Completed
Linear OptimizationProbabilityTheoretical Computer Science·Captain: mikedeng1

Greed Works – Online Algorithms For Unrelated Machine Stochastic Scheduling 2: Greedy Assignment With Nominal Start Times Is (7.216 + 3.608Δ)h(Δ)-Competitive in the Online-Time ModelResearch Paper

Scheduling jobs on parallel machines to minimize the total weighted completion time ∑jwjCj\sum_j w_jC_j∑j​wj​Cj​ is a basic model of service and computing systems. Two features of practice are hard to combine with performance guarantees: jobs are not known in advance but arrive over time, and their processing times are random, with only their distributions known when they…

12 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignProbability·Captain: mikedeng1

Approximate Revenue Maximization with Multiple Items 2: Selling Two I.I.D. Goods Separately Guarantees at Least e/(e + 1) ≈ 73% of the Optimal RevenueResearch Paper

A seller with several goods can sell them one at a time or offer a mechanism that links allocation and payment across goods. Separate selling asks the seller to solve a one-good pricing problem for each item. A general mechanism can offer lotteries and menus whose outcomes depend on the buyer's whole valuation vector. The difference matters because the…

13 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignProbability·Captain: mikedeng1

Approximate Revenue Maximization with Multiple Items 5: Bundling Is Optimal for Two I.I.D. Goods Whose Density on [a, ∞) Satisfies x f′(x) + (3/2) f(x) ≤ 0Research Paper

A seller with several goods and a single buyer of unknown, additive valuation faces the multi-dimensional revenue maximization problem. For one good the answer is classical: by Myerson's theorem (Myerson 1981) a single posted price is optimal. For two or more goods no such simplification exists in general: optimal mechanisms may randomize, may offer menus…

9 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainProbability·Captain: mikedeng1

Partially Observable Total-Cost Markov Decision Processes with Weakly Continuous Transition Probabilities 1: The Belief MDP Satisfies Assumption (W*) Under Total-Variation-Continuous ObservationsResearch Paper

A partially observable Markov decision process (POMDP) models a controller that cannot see the state of the system it steers, only noisy observations of it. Inventory control with unrecorded demand, machine maintenance with imperfect inspection, and target tracking from sensor readings all have this form. The standard way to solve a POMDP is to replace it…

16 thms4 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine Learning·Captain: mikedeng1

Regret in Online Combinatorial Optimization I: For Every Learning Rate the Exponentially Weighted Forecaster EXP2 Has Full-Information Regret at Least 0.01 d^{3/2}√n on Some Action SetResearch Paper

Online combinatorial optimization is a repeated game in which a learner selects, round after round, a structured object (a subset of fixed size, a path, a matching, a spanning tree) encoded as a 0/1 vector, and an adversary assigns a cost to every coordinate. It models routing, ranking, scheduling and many other sequential decision problems in operations…

7 thms4 active users
🏆Completed
OptimizationProbabilityStatistics·Captain: mikedeng1

Recovering Best Statistical Guarantees via the Empirical Divergence-Based Distributionally Robust Optimization 1: Empirical Burg-Ball DRO Bounds Cover E[h(x;ξ)] with Probability Tending to 1 − αResearch Paper

Stochastic programs and chance-constrained models in operations research contain expectations of the form

14 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryProbability·Captain: mikedeng1

Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals I: Under Random Arrival Order, Nonadaptive Thresholds Earn a 1 − 1/e Fraction of E[max Xᵢ]Research Paper

In a prophet inequality, a gambler sees prizes one at a time and must decide when to stop, while a prophet knows every realization and takes the largest. A stopping guarantee compares the gambler’s expected prize with the prophet’s. The order of arrival changes the problem: here the prizes are independent but can have different distributions, and every…

12 thms4 active usersReviewed
PreviousPage 16 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