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
Complexity TheoryLinear OptimizationOptimization+1·Captain: mikedeng1

A Comment on "Computational Complexity of Stochastic Programming Problems" 3: An ε-Optimal Decision of the Random-Recourse Program (11) Decides the Integer Feasibility ProblemResearch Paper

A linear two-stage stochastic program chooses a first-stage decision xxx before an uncertain parameter ξ~\tilde\xiξ~​ is revealed, and pays the optimal value Q(x,ξ)Q(x,\xi)Q(x,ξ) of a second-stage linear program once the realization ξ\xiξ is known. Such programs are the basic model of planning under uncertainty in operations research, and their computational complexity…

8 thms3 active usersReviewed
🏆Completed
AnalysisOptimization·Captain: mikedeng1

Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs 1: Every Cluster Point of the e-PSG Iterates Is a Lifted Stationary PointResearch Paper

A fractional program minimizes a ratio f(x)/g(x)f(x)/g(x)f(x)/g(x) over a set SSS. Nonconvex, nonsmooth ratios arise in the scale-invariant sparse signal recovery model min⁡∥x∥1/∥x∥2\min\|x\|_1/\|x\|_2min∥x∥1​/∥x∥2​ over a polyhedron, in robust Sharpe-ratio optimization in finance, and in the Rayleigh quotient x⊤Ax/x⊤Bxx^\top Ax/x^\top Bxx⊤Ax/x⊤Bx over a sphere; with g≡1g\equiv1g≡1 and S=HS=HS=H the problem reduces to composite…

13 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimal TransportOptimization·Captain: mikedeng1

Optimal Transport-Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes 2: The Dual Objective f_δ(β, λ) = E_P0[ℓ_rob(β, λ; X)] Is Proper and ConvexResearch Paper

Distributionally robust optimization (DRO) replaces the expected loss EP0[ℓ(βTX)]E_{P_0}[\ell(\beta^{\mathsf T}X)]EP0​​[ℓ(βTX)] of a decision β\betaβ under a baseline distribution P0P_0P0​ by its worst case over all distributions PPP that are close to P0P_0P0​. When closeness is measured by an optimal transport cost, the worst case over this infinite-dimensional ball has a one-dimensional dual:…

9 thms3 active usersReviewed
🏆Completed
OptimizationProbabilityStatistics·Captain: mikedeng1

From Data to Decisions: Distributionally Robust Optimization Is Optimal 1: The Relative-Entropy Robust Predictor Is the Least Conservative Predictor Whose Disappointment Decays at Rate rResearch Paper

A decision maker who must choose xxx before observing an uncertain outcome ξ\xiξ usually does not know the distribution of ξ\xiξ; only past observations ξ1,…,ξT\xi_1,\dots,\xi_Tξ1​,…,ξT​ are available. Data-driven optimization replaces the unknown expected cost by an estimate computed from the data. The simplest estimate, the sample average, is optimistically biased: the cost…

13 thms3 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryOptimization+1·Captain: mikedeng1

A Comment on "Computational Complexity of Stochastic Programming Problems" 2: The Expected Recourse Value of (10) Is 1 − Vol(P(S; ⪯)), and a 1/(2k!)-Accurate Value Counts Linear ExtensionsResearch Paper

A two-stage stochastic program chooses a first action before uncertainty is observed and then takes a recourse action after the observation. Evaluating the expected optimal recourse value can be difficult even when the recourse problem for each fixed observation is a small linear program. This mission isolates the example in Section 3 of Hanasusanto, Kuhn…

8 thms3 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

Constrained Assortment Optimization for the Nested Logit Model 7: Under Space Constraints, for Every α > 1, O(⌈α/(α−1)⌉ n^(⌈α/(α−1)⌉+2)) Candidate Assortments Include an α-Approximate SolutionResearch Paper

A retailer that sells products in categories must decide which products to offer in each category. When customers choose among the offered products according to the nested logit model, the expected revenue depends on the offered assortment in a nonlinear way, and the retailer's shelf space adds a knapsack constraint in every category. Gallego and Topaloglu (…

9 thms3 active usersReviewed
🏆Completed
Complexity TheoryOptimizationProbability+1·Captain: mikedeng1

A Comment on "Computational Complexity of Stochastic Programming Problems" 1: δ-Accurate Expected Recourse Values of Problem (2) Determine the #Parity Count of a Knapsack PolytopeResearch Paper

A two-stage stochastic program chooses a decision before uncertainty is observed and a recourse decision afterward. Its objective can involve the expected optimal value of the recourse problem. Even with linear constraints, evaluating that expectation can be difficult when the random input has many coordinates. Dyer and Stougie's 2006 complexity paper studie…

10 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates 1: Bounded Iterates Converge to a KKT Point with Finite Length Under the KL PropertyResearch Paper

Many problems in signal processing, statistics and machine learning are of the form min⁡x{g(Ax)+h(x)}\min_x \{g(Ax)+h(x)\}minx​{g(Ax)+h(x)}: a smooth data-fitting term hhh, plus a possibly nonsmooth and nonconvex regularizer ggg applied to a linear image AxAxAx of the variable. Examples are total-variation-type penalties with nonconvex potentials, ℓ0\ell_0ℓ0​-type sparsity terms, and constraints Ax∈CAx\in CAx∈C…

16 thms3 active usersReviewed
🏆Completed
Machine LearningOptimal TransportOptimization·Captain: mikedeng1

Regularization via Mass Transportation I: Wasserstein-Robust Linear Classification with Label Flipping Is a Finite Convex ProgramResearch Paper

A classifier trained from finitely many examples can perform well on those examples while responding poorly to changes in the feature distribution or to mislabeled observations. Distributionally robust learning addresses this by choosing a classifier against every probability distribution within a specified distance of the empirical distribution. The…

9 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Constrained Assortment Optimization for the Nested Logit Model 3: Under Cardinality Constraints, O(n²) Candidate Assortments per Nest Include an Optimal Solution of Problem (7) for Every u ≥ 0Research Paper

A retailer that decides which products to put on a shelf, or an airline that decides which fare classes to open, faces an assortment problem: the set of products offered changes which product a customer buys, and the firm wants the offer set that maximizes expected revenue. When customers first pick a category (a brand, a store aisle, a flight time) and…

6 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Constrained Assortment Optimization for the Nested Logit Model 2: If Each Nest's Candidates Include an α-Approximate Solution of Problem (7) for Every u ≥ 0, Some Combination Earns at Least Z*/αResearch Paper

A retailer chooses which products to offer, knowing that what customers buy depends on what is on the shelf. In the nested logit model (Williams 1977) products are grouped into nests, and a customer first picks a nest (or leaves) and then a product inside it. Choosing the offer set to maximize expected revenue is the assortment problem. In practice each…

7 thms3 active usersReviewed
🏆Completed
AnalysisConvex OptimizationOptimization·Captain: mikedeng1

A Primal-Dual Interior-Point Algorithm for Nonsymmetric Exponential-Cone Optimization 3: The Exponential-Cone Barrier Does Not Have Negative CurvatureResearch Paper

Interior-point methods for conic optimization are best understood on symmetric cones: the nonnegative orthant, the second-order cone and the cone of positive semidefinite matrices. On these cones the barrier functions are self-scaled, and Nesterov and Todd showed that every primal-dual pair (x,s)(x, s)(x,s) then has a unique scaling point www with s=F′′(w)xs = F''(w)xs=F′′(w)x and …

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

A Primal-Dual Interior-Point Algorithm for Nonsymmetric Exponential-Cone Optimization 1: Along the Combined Corrector Direction the Residuals and the Complementarity Gap Both Scale by 1 − α(1 − γ)Research Paper

Conic optimization over the exponential cone Kexp⁡=cl⁡{x∈R3:x1≥x2ex3/x2, x2>0}K_{\exp}=\operatorname{cl}\{x\in\mathbb R^3: x_1\ge x_2e^{x_3/x_2},\ x_2>0\}Kexp​=cl{x∈R3:x1​≥x2​ex3​/x2​, x2​>0} models entropy, relative entropy, logistic regression, log-sum-exp and geometric programming. Unlike the nonnegative orthant, the second-order cone and the semidefinite cone, the exponential cone is not symmetric (self-scaled), so the…

8 thms3 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem 2: The Best Lagrangean Bound of the Integer Relaxation RF Is at Least the LP Relaxation Bound, Sometimes StrictlyResearch Paper

In two-echelon distribution goods travel from a central depot to intermediate facilities, called satellites, on large first-level vehicles, and from the satellites to customers on smaller second-level vehicles. City logistics schemes that keep heavy trucks out of urban centres are the standard example. The two-echelon capacitated vehicle routing problem (2E-…

12 thms3 active users
🏆Completed
Convex OptimizationNumerical AnalysisOptimization·Captain: mikedeng1

Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 3: For Block-Constrained Problems, Uniform Coordinate Descent Has Rate n/(n + k), Linear Under Strong ConvexityResearch Paper

Coordinate descent methods update one block of variables at a time. They are the method of choice when the number of variables is so large that even one full gradient is too expensive, while a single partial derivative is cheap: support vector machines, ℓ1\ell_1ℓ1​-regularized regression, and large sparse least-squares problems are the standard examples. Yu.…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOptimization·Captain: mikedeng1

Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 4: Accelerated Coordinate Descent ACDM Has Expected Error at Most (n/(k + 1))²·(2‖x₀ − x*‖₁² + (f(x₀) − f*)/n²)Research Paper

Coordinate descent methods update one block of variables at a time. For problems with millions or billions of variables, where even one full gradient is too expensive to compute or store, a step that touches a single block can be orders of magnitude cheaper than a full gradient step. Nesterov's Efficiency of coordinate descent methods on huge-scale…

11 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem 3: Every Solution Cheaper Than an Upper Bound Uses a Configuration of First-Level Routes Passing the Pruning TestsResearch Paper

City logistics often moves goods in two stages: large trucks bring freight from a central depot to a few intermediate satellites, and small vehicles distribute it from the satellites to the customers. The two-echelon capacitated vehicle routing problem (2E-CVRP) is the basic optimization model of such systems; it contains the capacitated location-routing…

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

Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 2: On a Regularized Objective, RCDM(1, x₀) Finds an ε-Solution with Probability ≥ β Within the Iteration Bound (3.11)Research Paper

Randomized coordinate descent updates one block of variables per iteration, chosen at random. For problems whose dimension makes even one full gradient expensive (the "huge-scale" problems of the title, such as sparse least squares or truss topology design), a coordinate step can cost a tiny fraction of a gradient step. Nesterov's paper (CORE Discussion…

6 thms3 active usersReviewed
🏆Completed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

Matroid Prophet Inequalities 2: On an Intersection of p Matroids, the Summed-Threshold Algorithm Earns at Least 1/(4p−2) of the Expected OptimumResearch Paper

A prophet inequality compares a gambler who sees independent random rewards one at a time, and must accept or reject each on arrival, with a prophet who sees all rewards in advance. The classical inequality of Krengel, Sucheston and Garling (1977–78, as cited in the paper) says that when only one reward may be kept, a single threshold rule earns at least…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOptimization·Captain: mikedeng1

Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 1: Random Block Coordinate Descent RCDM(α, x₀) Has Expected Error at Most 2·S_α·R²_{1−α}(x₀)/(k + 4)Research Paper

Many large optimization problems arising in machine learning, statistics and network analysis have so many variables that computing a single full gradient is already expensive, while a single partial derivative, or a gradient with respect to a small block of variables, is cheap. Coordinate descent methods exploit this: at each iteration they update one…

11 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Quantity Flexibility Contracts and Supply Chain Performance 1: Under the Minimum Commitment Policy a Flex Node With At Least Its Customer's Flexibility Keeps Zero InventoryResearch Paper

Manufacturers and their suppliers rarely trade on fixed orders. A buyer sends a rolling schedule of intended purchases for the coming periods and revises it every period as its own forecasts change. Left unconstrained, such revisions pass demand volatility up the supply chain and amplify it, the phenomenon studied as the bullwhip effect (Lee, Padmanabhan &…

6 thms3 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraOptimization·Captain: mikedeng1

On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues: If m > k(n − k), Extreme Optima of Affine EV_k Have λ_k = λ_{k+1} with Multiplicity ≥ n − τResearch Paper

Minimizing the sum of the kkk largest eigenvalues of a symmetric matrix that depends affinely on parameters is a basic problem of eigenvalue optimization (survey: A. S. Lewis and M. L. Overton, Eigenvalue optimization, Acta Numerica 5, 1996, doi:10.1017/S0962492900002646). Its objective is convex, and fkf_kfk​ is differentiable at BBB exactly when …

14 thms3 active usersReviewed
🏆Completed
Probability·Captain: mikedeng1

A Single-Item Inventory Model for a Nonstationary Demand Process: With Adaptive Base-Stock Control at Two Stages, Upstream Inventory Is N(y₀, σ²∑_{i<K}(1+(L+i)α)²)Research Paper

Classical safety-stock formulas assume that demand is stationary: independent and identically distributed around a fixed mean. Many products do not behave that way. Their demand level drifts, and the forecast has to follow it. Graves (A single-item inventory model for a nonstationary demand process, Manuf. Serv. Oper. Manag. 1(1):50–61, 1999) works out what…

12 thms3 active usersReviewed
🏆Completed
Probability·Captain: mikedeng1

A Note on Probability Distributions with Increasing Generalized Failure Rates II: For IGFR X with Support (α, ∞) and g(ξ) → κ, E[Xⁿ] Is Finite iff κ > nResearch Paper

Many models in operations management and economics need the demand or valuation distribution to be regular in some way, so that an optimal price, order quantity or contract is unique. Pricing a service to one customer whose valuation XXX has survival function Φˉ\bar\PhiΦˉ is a typical example. The seller maximizes p Φˉ(p)p\,\bar\Phi(p)pΦˉ(p). The first-order condition is …

14 thms3 active usersReviewed
🏆Completed
Linear OptimizationTheoretical Computer Science·Captain: mikedeng1

AdWords and Generalized On-line Matching I: The Tradeoff Algorithm with ψ_k(i) = Σ_{j≥i} y*_j Is (1 − 1/e)-Competitive as k → ∞ When Bids Are SmallResearch Paper

Search engines sell advertising space query by query. Each advertiser states a bid for each keyword and a daily budget; queries arrive one at a time, and each must be assigned to an advertiser immediately, without knowledge of the queries still to come. The revenue-maximizing assignment of the day can only be computed offline. The adwords problem asks how…

9 thms3 active usersReviewed
PreviousPage 47 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