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

Open932Completed2682All3614
🏆Completed
Bandit AlgorithmsMachine LearningProbability·Captain: mikedeng1

Stochastic Linear Optimization under Bandit Feedback 2: A Regret Lower Bound on the CircleResearch Paper

In stochastic linear optimization under bandit feedback a learner repeatedly chooses a point xtx_txt​ from a compact decision set D⊂RnD\subset\mathbb R^nD⊂Rn and observes only the random cost ℓt\ell_tℓt​ of that point, whose mean is μ⋅xt\mu\cdot x_tμ⋅xt​ for an unknown vector μ\muμ. The problem models online routing, ad placement and other sequential decisions with linearly structured…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization·Captain: mikedeng1

On Certain Polytopes Associated with Graphs IV: Adjacent Stable Sets on the Stable Set PolytopeResearch Paper

Many combinatorial optimization problems are linear programs over a polytope whose vertices are the zero–one incidence vectors of the feasible objects: matchings, stable sets, spanning trees. The edges of such a polytope (pairs of vertices joined by a one-dimensional face) govern the behaviour of the simplex method and of local-search procedures, which move…

6 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization·Captain: mikedeng1

On Certain Polytopes Associated with Graphs II: No Clique Is a Cutset of a Connected α-Critical GraphResearch Paper

The stability number α(G)\alpha(G)α(G) of a graph, the largest number of pairwise non-adjacent vertices, is the optimum of an integer program over the stable set polytope P(G)P(G)P(G). Linear programming duality turns any explicit linear description of P(G)P(G)P(G) into a certificate of optimality for α(G)\alpha(G)α(G), which is why the question "which inequalities are needed to describe …

8 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization·Captain: mikedeng1

On Certain Polytopes Associated with Graphs I: Clique Inequalities Define the Stable Set Polytope Exactly for Perfect GraphsResearch Paper

Many combinatorial optimization problems ask for the best subset of a finite set subject to combinatorial side conditions. The polyhedral method replaces the finite family of feasible subsets by the convex hull of their incidence vectors and asks for an explicit system of linear inequalities describing that convex hull; once such a system is known, linear…

8 thms2 active usersReviewed
🏆Completed
OptimizationProbabilityTheoretical Computer Science·Captain: mikedeng1

An Optimal On-Line Algorithm for Metrical Task System 2: The Randomized Competitive Ratio of the Uniform Task System Lies Between H(n) and 2H(n)Research Paper

Metrical task systems, introduced by Borodin, Linial and Saks (J. ACM 39(4), 1992), are a common abstraction of on-line problems in which a server occupies one of finitely many states, pays a cost for each task depending on its current state, and may pay a transition cost to change state first. Paging, list update and the kkk-server problem all fit into this…

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

An Optimal On-Line Algorithm for Metrical Task System 1: Every n-State Metrical Task System Has Competitive Ratio 2n - 1Research Paper

A system that processes a stream of tasks can often be configured in several ways, and the configuration affects both the cost of the current task and the cost of switching before the next one: paging schemes, replicated files, server placements. When the future is unknown, the natural worst-case yardstick is competitive analysis, introduced by Sleator and…

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

Nonmonotone Spectral Projected Gradient Methods on Convex Sets I: SPG2 Is Well Defined and Its Accumulation Points Are StationaryResearch Paper

Minimizing a smooth function over a closed convex set Ω⊆Rn\Omega\subseteq\mathbb R^nΩ⊆Rn on which projection is cheap (a box, a ball, a simplex) is a routine subproblem in large-scale optimization: box-constrained minimization is the inner solver of augmented Lagrangian methods, and bound-constrained least squares, image restoration and density estimation all have…

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

Robust Solutions of Optimization Problems Affected by Uncertain Probabilities II: A Self-Concordant Barrier for the Perspective ConstraintResearch Paper

Robust optimization protects a decision against every scenario in an uncertainty set. When the uncertain data are probabilities, a natural uncertainty set is a ball around a nominal distribution measured by a φ-divergence (Kullback–Leibler, Burg entropy, χ², Hellinger and others). Ben-Tal, den Hertog, De Waegenaere, Melenberg and Rennen (Management Science…

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

Robust Solutions of Optimization Problems Affected by Uncertain Probabilities I: The Robust Counterpart of a Linear Constraint under φ-Divergence UncertaintyResearch Paper

Many decision problems contain a constraint whose coefficients are an expectation under a probability vector that is not known exactly: an expected cost under uncertain scenario probabilities, an expected payoff of an asset under an estimated distribution, the expected demand in a newsvendor model. The probabilities are usually estimated from data, and a…

12 thms2 active usersReviewed
🏆Completed
Markov ChainProbabilityStochastic Systems·Captain: mikedeng1

Open, Closed, and Mixed Networks of Queues with Different Classes of Customers: The Product-Form Equilibrium DistributionResearch Paper

Networks of queues model computer systems, communication networks and manufacturing lines: customers (jobs, packets, parts) move between service centers, wait, receive service and move on. Their equilibrium behaviour determines throughputs, utilizations and response times, and for most networks it can only be computed by solving the full balance equations…

9 thms2 active usersReviewed
🏆Completed
Mechanism Design·Captain: naimengye

Fundamentals of Supply Chain Theory XIII: AuctionsTextbook

The Vickrey-Clarke-Groves auction is the textbook mechanism for selling several objects at once: bidders report valuations for bundles, the auctioneer computes the welfare-maximizing allocation, and each winner pays the externality it imposes on the others. Truthful bidding is a dominant strategy and the outcome is efficient. Yet Ausubel and Milgrom (2006)…

5 thms2 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: naimengye

The Theory and Practice of Revenue Management V: CompetitionTextbook

Revenue management is practised by firms that compete: airlines matching fares while allocating seats, retailers ordering stock and then pricing to clear it, hotels protecting rooms for late high-paying guests. Chapter 8 of Talluri and van Ryzin's The Theory and Practice of Revenue Management (2004) surveys the economics behind these situations: monopoly…

8 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: naimengye

Fundamentals of Supply Chain Theory XII: The Vehicle Routing ProblemTextbook

The vehicle routing problem asks for the cheapest set of delivery routes from a depot to a set of customers when each vehicle can carry only so much. It generalizes the traveling salesman problem, which is the case of a single vehicle of unlimited capacity, and it is the operational problem behind every distribution fleet. Exact methods reach a few hundred…

5 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: naimengye

Fundamentals of Supply Chain Theory XI: The Traveling Salesman ProblemTextbook

A salesman must visit nnn cities and return home by the shortest route. The traveling salesman problem is the prototype of combinatorial optimization: easy to state, NP-hard (Karp 1972), and solved to optimality on instances with tens of thousands of nodes by branch-and-cut. In a supply chain it is the core of every vehicle routing model and of the…

15 thms2 active usersReviewed
🏆Completed
Optimization·Captain: naimengye

The Theory and Practice of Revenue Management III: Dynamic PricingTextbook

A retailer marking down a seasonal line, an airline raising fares as seats sell, a manufacturer pricing while restocking: each sets prices over time against a finite and changing inventory. Chapter 5 of Talluri and van Ryzin's The Theory and Practice of Revenue Management (2004) collects the structural theory of that problem. Without replenishment, the…

5 thms2 active usersReviewed
🏆Completed
Markov Chain·Captain: naimengye

Fundamentals of Supply Chain Theory X: Supply UncertaintyTextbook

Every model in the earlier chapters of this series treats demand as the uncertain quantity and supply as given. Chapter 9 of Snyder and Shen's Fundamentals of Supply Chain Theory (2019) reverses the roles: demand is deterministic and the supplier fails. A disruption is a binary event, modeled as a two-state Markov process between up and down periods, during…

6 thms2 active usersReviewed
🏆Completed
Optimization·Captain: naimengye

Fundamentals of Supply Chain Theory IX: Facility Location ModelsTextbook

Choosing where to open distribution centers is the strategic decision that fixes a supply chain's shape for years. The basic model, the uncapacitated fixed-charge location problem (UFLP) of Balinski (1965), trades the fixed cost of opening sites against the cost of transporting demand from open sites to customers. It is NP-hard, yet routinely solved to…

10 thms2 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: naimengye

Fundamentals of Supply Chain Theory VIII: Supply Chain ContractsTextbook

A retailer facing uncertain single-period demand and buying from a supplier at a wholesale price orders less than the two of them together would want. The reason is not irrationality but incentives: the retailer bears the whole cost of unsold stock while the supplier collects a margin on every unit ordered, so each party marks up its own cost and the…

11 thms2 active usersReviewed
🏆Completed
Optimization·Captain: naimengye

Inventory Control VII: Multi-Echelon Lot Sizing and Roundy's 98 % ApproximationTextbook

Chapter 9 of Axsäter's Inventory Control opens with the observation that in a multi-echelon system it is not optimal to choose batch quantities installation by installation: the batch at one site is the demand pattern of the next site upstream. Even with constant customer demand the exact optimum can be complicated, and the book's Example 9.4 shows a…

11 thms2 active usersReviewed
🏆Completed
OptimizationProbability·Captain: naimengye

Inventory Control VI: Optimality of (R, Q) Policies When Ordering in BatchesTextbook

Every model in Chapters 5 and 6 of Axsäter's Inventory Control assumes at the outset that the ordering policy is of (R,Q)(R,Q)(R,Q) or (s,S)(s,S)(s,S) type. Section 6.2 asks whether better policies exist and answers, for the case in which there are no ordering costs but every order must be a multiple of a fixed batch quantity QQQ, that none do: Proposition 6.1, "an (R,Q)(R,Q)(R,Q) policy…

10 thms2 active usersReviewed
🏆Completed
OptimizationProbability·Captain: naimengye

Inventory Control V: Joint Optimization of Reorder Point and Batch QuantityTextbook

An (R,Q)(R,Q)(R,Q) policy has two parameters. Chapter 4 of Axsäter's Inventory Control chooses the batch quantity QQQ from a deterministic model, and Chapter 5 chooses the reorder point RRR from a stochastic one with QQQ held fixed; the book presents this two-step practice as an adequate approximation. Section 6.1 asks what is lost by it and shows how to optimize both…

9 thms2 active usersReviewed
🏆Completed
OptimizationProbability·Captain: naimengye

Inventory Control IV: Reorder Points under Normally Distributed DemandTextbook

Chapter 4 of Axsäter's Inventory Control fixes the batch quantity QQQ from a deterministic model, and Chapter 5 asks the question that deterministic models cannot answer: with demand random and a replenishment lead-time LLL, when should the next batch be ordered? Under a continuous review (R,Q)(R,Q)(R,Q) policy the answer is a single number, the reorder point RRR, and…

16 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: naimengye

Complex Scheduling III: Interval Consistency Tests for the RCPSPTextbook

Exact methods for the resource-constrained project scheduling problem — branch-and-bound over activity lists or over start-time assignments, and the lower-bound computations inside them — live or die by how much of the search space can be discarded before it is enumerated. The standard tool is constraint propagation: deducing, from the precedence, resource…

9 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: naimengye

Scheduling Algorithms V: Preemptive Scheduling on Uniform MachinesTextbook

When several processors share a workload, the first question is how long the workload takes if it is spread out as well as possible. If a job may be interrupted and resumed later, possibly on another processor — preemption, the setting of operating systems, of communication links and of any resource that can be time-shared — the answer is a closed formula,…

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

The Design of Competitive Online Algorithms via a Primal-Dual Approach IX: General Packing-Covering ConstraintsTextbook

Chapter 4's framework (formalized in this series' 04-framework mission) solves the online covering-packing pair only in the restricted setting a(i,j) ∈ {0,1}, b(j) = 1 — every constraint is an unweighted "cover me with at least one of these" condition. Chapter 14 delivers the promise made at the very start of the survey (p. 115: "we show how to extend the…

7 thms2 active usersReviewed
PreviousPage 106 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