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
Algorithmic Game TheoryMechanism DesignProbability·Captain: mikedeng1

Bargaining under Incomplete Information II: The Linear Equilibrium of the Sealed-Offer Rule for Uniform ValuesResearch Paper

A buyer and a seller negotiate over one indivisible good. Each knows the good's worth to themselves but not to the other side, so each shades their offer to exploit the other's uncertainty, and some mutually profitable trades fail. Chatterjee and Samuelson (Bargaining under Incomplete Information, Operations Research 31(5), 1983) modelled this as a one-shot…

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

Maximizing Non-Monotone Submodular Functions III: Guarantees of Deterministic Local SearchResearch Paper

Many optimization problems ask for a subset of a finite ground set that maximizes a function with diminishing returns: the cut of a graph or a directed graph, the value of a facility-location configuration, the entropy of a set of random variables, or a welfare function in combinatorial auctions. These functions are submodular but typically non-monotone:…

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

The Generalized Quasi-Variational Inequality Problem III: The Projection Map Is a Contraction and Its Iterates Converge to a SolutionResearch Paper

A variational inequality asks for a point xxx of a set K⊆RnK\subseteq\mathbb R^nK⊆Rn at which a vector field fff points "into" KKK: (x′−x)Tf(x)≥0(x'-x)^T f(x)\ge 0(x′−x)Tf(x)≥0 for every x′∈Kx'\in Kx′∈K. It is the common form of the first-order optimality conditions of constrained optimization, of complementarity problems, and of equilibrium models in economics and traffic networks. In many of these…

7 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

Projected Gradient Methods for Linearly Constrained Problems III: Finite Termination of a Gradient Projection Algorithm for Quadratic ProgrammingResearch Paper

Quadratic programming, the minimisation of a quadratic function subject to linear inequality constraints, is a basic subproblem of nonlinear optimisation (sequential quadratic programming, trust-region methods) and a model in its own right in portfolio selection, least-squares estimation and control. The classical solution methods are active-set methods:…

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

On Certain Polytopes Associated with Graphs III: The Stable Set Polytope after Substituting a Graph for a VertexResearch Paper

Many combinatorial optimization problems on graphs are linear programs over a polytope whose inequality description is unknown. The stable set polytope is the standard example: maximizing a linear function over it is the maximum weight stable set problem, which is NP-hard, and no complete inequality description is known for general graphs. A productive line…

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

Projected Gradient Methods for Linearly Constrained Problems II: Finite Identification of the Active Constraints at a Nondegenerate PointResearch Paper

Minimizing a smooth function subject to linear inequality constraints is the core subproblem of much of nonlinear optimization: bound-constrained problems, quadratic programs, and the subproblems of sequential quadratic programming and augmented Lagrangian methods all have this form. Methods for these problems are usually built from two parts, one that…

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

Nonmonotone Spectral Projected Gradient Methods on Convex Sets II: SPG1 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…

11 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOptimization·Captain: mikedeng1

Generalization Bounds in the Predict-then-Optimize Framework IV: Distance to Degeneracy and the Strength Property for PolytopesResearch Paper

Many decision problems in operations research are solved in two stages: a model predicts the unknown cost vector of a linear optimization problem from features, and the predicted costs are then passed to a solver. The smart predict-then-optimize (SPO) loss of Elmachtoub and Grigas measures the quality of a prediction by the excess true cost of the decision…

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

Local Search Heuristics for k-Median and Facility Location Problems II: p-Swap Local Search for k-Median Has Locality Gap 3 + 2/pResearch Paper

The k-median problem asks to open kkk facilities among a set of candidate sites so that the total distance from clients to their nearest open facility is as small as possible. It is a basic model of facility location and of clustering, and it is NP-hard, so the question studied in approximation algorithms is how close a polynomial-time method can get to the…

8 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

A Nonmonotone Line Search Technique and Its Application to Unconstrained Optimization I: Global Convergence to Stationary PointsResearch Paper

Line searches are the step-size rules inside most methods for smooth unconstrained minimization min⁡x∈Rnf(x)\min_{x \in \mathbb{R}^n} f(x)minx∈Rn​f(x): steepest descent, conjugate gradient, quasi-Newton and limited-memory methods all choose a direction dkd_kdk​ and then a step αk\alpha_kαk​ along it. Classical Armijo and Wolfe rules are monotone: they require f(xk+1)<f(xk)f(x_{k+1}) < f(x_k)f(xk+1​)<f(xk​). Grippo,…

15 thms2 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: mikedeng1

Monotonic Solutions of Cooperative Games 2: The Shapley Value Is the Unique Symmetric Strongly Monotonic Allocation ProcedureResearch Paper

Cost and benefit allocation problems arise whenever several parties share a joint undertaking: towns building a common water supply, divisions of a firm sharing overhead, users of a multi-purpose reservoir. They are modelled as cooperative games, and a rule that divides the joint value among the players is an allocation procedure. The standard such rule,…

15 thms2 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

Optimal Pricing of Seasonal Products in the Presence of Forward-Looking Consumers 4: Optimal Prices and Discount Time with Myopic Customers and Identical Declining ValuationsResearch Paper

Retailers of fashion and seasonal goods sell a fixed stock over a short season and routinely cut the price part-way through it. The markdown trades off two effects: a late discount keeps early, high-valuation customers paying the full price, while an early discount reaches customers whose interest in the product fades as the season goes on. Aviv and Pazgal (…

9 thms2 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

A Distributional Interpretation of Robust Optimization III: Uncertainty Set Shrinkage Approximates a Two-Scenario Distributionally Robust ProblemResearch Paper

Robust optimization (RO) protects a decision against every parameter value in an uncertainty set. For a decision vvv and a parameter x∈Rmx \in \mathbb{R}^mx∈Rm with objective f(v,x)f(v, x)f(v,x) to be maximized, the robust problem around a nominal parameter x0x_0x0​ with a deviation set Δ\DeltaΔ is

7 thms2 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

A Distributional Interpretation of Robust Optimization I: Robust Optimization over Overlapping Uncertainty Sets Equals a Distributionally Robust Stochastic ProgramResearch Paper

Robust optimization (RO) protects a decision against every realisation of an uncertain parameter in a prescribed uncertainty set; distributionally robust stochastic programming (DRSP) protects it against every probability distribution in a prescribed distribution set. The two paradigms are usually treated separately. When the n uncertain parameters live in…

5 thms2 active usersReviewed
🏆Completed
Discrete GeometryLinear OptimizationOptimization·Captain: mikedeng1

Maximal Lattice-Free Convex Sets in Linear Subspaces II: Minimal Valid Inequalities Come from Maximal Lattice-Free Convex SetsResearch Paper

Cutting planes for mixed-integer linear programs are often derived from a few rows of an optimal simplex tableau. Keeping qqq rows for basic integer variables x1,…,xqx_1,\dots,x_qx1​,…,xq​, dropping the nonnegativity of xxx (Gomory's corner polyhedron, Gomory 1969) and then the integrality of the nonbasic variables leaves the set of s≥0s\ge0s≥0 with f+∑jrjsj∈Zqf+\sum_j r^js_j\in\mathbb Z^qf+∑j​rjsj​∈Zq.…

16 thms2 active usersReviewed
🏆Completed
ProbabilityStochastic Systems·Captain: Shuze Chen

Processing Networks VII: Global Stability, Rings, and the Rybko–Stolyar BoundaryTextbook

Mission VI showed that two structural families of queueing networks — feedforward routing, and any network under HLSPS control — are stable throughout their entire subcritical region: no extra condition beyond the standard load condition is ever needed. Until the early 1990s it was widely conjectured that this held for every queueing network. Rybko and…

13 thms2 active usersReviewed
🏆Completed
ProbabilityStochastic Systems·Captain: Shuze Chen

Processing Networks VI: Feedforward and Generalized Jackson Network StabilityTextbook

Mission V supplied the general Lyapunov machinery — the extinction criteria of Lemmas 8.5, 8.6 and 8.11 — but a Lyapunov function does not construct itself. For a specific network structure and control policy, one must exhibit a concrete function and verify the drift condition. J. G. Dai and J. Michael Harrison's Processing Networks: Fluid Models and…

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

Existence of an Equilibrium for a Competitive Economy I: Equilibrium Exists When Every Consumer Can Trade Every GoodResearch Paper

Walras (1874) described an economy as a system of simultaneous equations, one per market, and argued that a set of prices clearing all markets exists because the number of equations equals the number of unknowns. Counting equations proves nothing, and the question of whether competitive equilibrium exists at all remained open for eighty years. Wald…

16 thms2 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

An Interactive Weighted Tchebycheff Procedure for Multiple Objective Programming I: In the Finite Case the Augmented Weighted Tchebycheff Program Characterizes the Nondominated SetResearch Paper

A decision problem with several conflicting objectives, such as cost, risk and service level, has no single optimum. What it has is a set of nondominated outcomes: those that cannot be improved in one objective without being worsened in another. Interactive methods of multiple objective programming search this set with a decision-maker, and at each step…

11 thms2 active usersReviewed
🏆Completed
Linear OptimizationMachine LearningOptimal Transport+2·Captain: mikedeng1

Distributionally Robust Logistic Regression II: Worst- and Best-Case Misclassification Risks over a Wasserstein Ball Are Linear ProgramsResearch Paper

A logistic regression model is fitted on finitely many samples, and the quantity a practitioner cares about is the misclassification risk of the fitted classifier on new data. Its empirical counterpart, the training error, is biased downwards, and classical generalization bounds give it an additive margin that depends on a complexity measure of the model…

8 thms2 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimal Transport+1·Captain: mikedeng1

Distributionally Robust Logistic Regression I: The Worst-Case Expected Logloss over a Wasserstein Ball Is a Tractable Convex ProgramResearch Paper

Logistic regression is among the most widely used classification methods in statistics and machine learning. Its maximum-likelihood estimator minimizes the average logloss on the training data and is known to overfit when data are scarce; practitioners respond with ad hoc regularization, typically a norm penalty on the weight vector. Shafieezadeh-Abadeh,…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsConvex OptimizationGraph Theory·Captain: mikedeng1

Cones of Matrices and Set-Functions and 0–1 Optimization IV: Clique, Odd Hole, Odd Wheel and Odd Antihole Constraints Hold after One Round of N₊Research Paper

The stable set problem (find a largest, or maximum-weight, set of pairwise non-adjacent nodes in a graph) is NP-hard, and its linear programming relaxations have been studied since the 1970s as a test bed for polyhedral combinatorics. Lovász and Schrijver (SIAM J. Optim. 1991) introduced a general lift-and-project procedure for 0–1 programs: lift a…

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

Approximation Algorithms for Combinatorial Problems IV: Greedy Set Cover C1 Has Worst-Case Ratio H(k) on SC(k)Research Paper

Set covering asks for the fewest members of a family of sets whose union is everything the family covers. It models crew scheduling, facility siting, test-suite reduction, logic minimization and fault testing; Johnson names the last two as its practical applications. Karp showed in 1972 that the decision version is NP-complete (Karp 1972), so in practice…

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

Approximation Algorithms for Combinatorial Problems II: The Greedy Literal Algorithm B1 Has Worst-Case Ratio (k+1)/k on MS(k)Research Paper

Maximum satisfiability asks for a truth assignment satisfying as many clauses of a propositional formula as possible. The paper notes that the restriction MS(k)MS(k)MS(k), in which every clause has at least kkk literals, is polynomial complete for every k≥1k \ge 1k≥1, so exact optimization is out of reach in general and one asks instead how close a fast algorithm is…

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

Approximation Algorithms for Combinatorial Problems I: The Subset-Sum Algorithms A_k Have Worst-Case Ratio (k+1)/kResearch Paper

David S. Johnson's 1974 paper Approximation Algorithms for Combinatorial Problems (J. Comput. System Sci. 9 (1974) 256–278) is one of the founding papers of the theory of approximation algorithms. It asks, for optimization problems whose decision versions Karp had just shown to be polynomial complete, how close a fast heuristic can be guaranteed to come to…

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