Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Linear Optimization

468 missions · 368 completed

Missions

Open100Completed368All468
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Secretaries with Advice 4: With Advice from a Binary Classifier, a Threshold Policy Is OptimalResearch Paper

The classical secretary problem asks a decision maker to choose the best of nnn candidates arriving in random order. A decision must be made when each candidate arrives, before later candidates are seen. In the classical model the decision maker sees only comparisons with earlier candidates. In hiring and selection, a prediction system may also classify an…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Secretaries with Advice 2: With k Samples, a Threshold Policy Is Optimal for Selecting the Best of n SecretariesResearch Paper

In the classical secretary problem, nnn candidates with distinct qualities arrive in uniformly random order; after each arrival one sees only how the current candidate compares with those already seen, and must irrevocably accept or reject. The goal is to accept the best candidate. Dynkin's rule (skip roughly n/en/en/e candidates, then accept the first one better…

16 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex Optimization·Captain: mikedeng1

Persuading Risk-Conscious Agents: A Geometric Approach II: In Binary Persuasion with a Convex Non-Adoption Region the Convex Program Reduces to a Linear Program over Ω ∪ K₀₁Research Paper

In Bayesian persuasion a sender who observes the state of the world commits to a signaling scheme, a receiver updates her belief by Bayes' rule and acts, and the sender chooses the scheme that maximizes her own expected payoff (Kamenica and Gentzkow 2011). The classical theory assumes the receiver maximizes expected utility, so her payoff is linear in her…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Reducing Marketplace Interference Bias Via Shadow Prices 2: In Expectation the Shadow-Price Estimator Equals the Derivative of the Finite-Sample Partial-Treatment Value FunctionResearch Paper

Two-sided platforms (ride hailing, delivery, freight, cloud capacity) test product changes with user-split experiments: each arriving demand unit is assigned to treatment with probability ρ\rhoρ and to control otherwise. Treated and control units then compete for the same supply, so the outcome of one group depends on the size of the other. This interference b…

9 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

On Solving Multistage Stochastic Programs with Coherent Risk Measures: The Inner-Approximation Policy's Nested Risk-Adjusted Cost Is at Most the Upper Bound yResearch Paper

Multistage stochastic linear programs model decisions taken over time under uncertainty: reservoir releases in hydro-thermal scheduling, production and inventory plans, capacity expansion. Their standard solution method, stochastic dual dynamic programming (SDDP, Pereira and Pinto 1991), approximates each stage's cost-to-go function from below by cutting…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Production Scheduling for Strategic Open Pit Mine Planning: A Mixed-Integer Programming Approach 2: Clique and Lifted Clique Cuts on Pairwise Incompatible Clusters Are ValidResearch Paper

Strategic open pit mine planning decides which parts of an ore body are excavated, when, and where each block of material is sent. Rivera Letelier, Espinoza, Goycoolea, Moreno and Muñoz (Operations Research 68(5), 2020) model the problem as a mixed-integer program, the precedence-constrained production scheduling problem with clusters (PCPSP-C),…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Production Scheduling for Strategic Open Pit Mine Planning: A Mixed-Integer Programming Approach 1: Under G, g ≥ 0 Every Minimal Optimal Schedule Stays inside the Ultimate Pit LimitResearch Paper

Strategic planning of an open pit mine decides, over a horizon of 20 to 50 years, which parts of an ore body are excavated, when, and where the excavated material is sent. A deposit is discretized into blocks, often millions of them, and the decisions are constrained by wall-slope precedences between blocks, by mining and processing capacities, and by…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Production Scheduling for Strategic Open Pit Mine Planning: A Mixed-Integer Programming Approach 4: Hourglass Production Cuts Are Valid under Full and Partial IntegralityResearch Paper

Strategic open pit mine planning decides which parts of an ore body are excavated, in which period, and to which destination (a processing plant, a stockpile, a waste dump) each block of material is sent. Rivera Letelier, Espinoza, Goycoolea, Moreno and Muñoz (Operations Research 68(5), 2020) model this as a mixed-integer program, the precedence-constrained…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Multistage Adaptive Robust Optimization for the Unit Commitment Problem II: Under the W_it-Policy, Robust Generation and Ramping Limits Reduce to the Extreme Total-Load ScenariosResearch Paper

Unit commitment (UC) is the daily scheduling problem of electricity system operators: decide which generators are switched on in each hour of the next day, and how much each produces, so that supply meets the net load at minimum cost while respecting generation limits, ramping limits and transmission limits. With growing shares of wind and solar power, the…

6 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

K-Adaptability in Two-Stage Robust Binary Programming 5: The ε-Approximation (6ε) Is Equivalent to the Mixed-Integer Bilinear Program (7)Research Paper

Two-stage robust optimization models decisions taken in two steps around an uncertain parameter: a first-stage decision xxx is fixed before a parameter ξ\xiξ is revealed from an uncertainty set Ξ\XiΞ, and a second-stage (recourse) decision yyy is taken afterwards. When the recourse is binary (whether to open a facility, route a vehicle, schedule a task), the exact…

12 thms3 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

Fast Rates for Contextual Linear Optimization 3: Under the Margin Condition, a Plug-In Policy Whose Estimate Has Pointwise Sub-Gaussian Tails at Rate aₙ Has Regret O(B·aₙ^(−(1+α)/2))Research Paper

Many operational decisions are linear programs whose cost vector is uncertain but predictable from side information: routing with travel times that depend on weather and time of day, procurement with prices that depend on market signals, assignment with costs that depend on observed features. Contextual linear optimization (CLO) formalizes this: observe…

9 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization·Captain: mikedeng1

Minimum Cost Flows in Graphs with Unit Capacities: When the Second Phase of a Cost Scale Starts, at Most 3λ Excess Is Left for λ = √m and 36λ for λ = n^(2/3)Research Paper

Minimum-cost flow is a standard model for routing a quantity through a network while paying a cost on each arc. Unit capacities arise when each input arc can carry at most one unit; they include flow formulations of several matching and assignment problems. Goldberg, Kaplan, Hed and Tarjan analyze a cost-scaling algorithm for this setting. Their…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications: With Fixed Pick-up Times, the Offline Taxi Routing MIO Formulation (5)-(14) Is IntegralResearch Paper

Taxi fleets, ride-hailing services and dial-a-ride systems assign incoming customer requests to vehicles under time constraints. Bertsimas, Jaillet and Martin (Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications, Operations Research 67(1), 2019) model the online taxi routing problem, a special case of the online dial-a-ride problem…

5 thms3 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: mikedeng1

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy 2: The LP Algorithm Decides PCSPs with Majority or Alternating-Threshold Polymorphisms of All Odd AritiesResearch Paper

A constraint satisfaction problem (CSP) asks whether variables can be assigned values so that every constraint of a given instance holds. Feder and Vardi conjectured, and Bulatov and Zhuk proved in 2017, that every CSP over a finite set of relations is either polynomial-time solvable or NP-complete, and that the answer is governed by the polymorphisms of…

10 thms3 active usersReviewed
🏆Completed
Complexity TheoryOperations ResearchOptimization+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
Operations ResearchOptimization·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
Operations ResearchOptimization·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
Operations ResearchTheoretical 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
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Stochastic Machine Scheduling with Precedence Constraints 1: LP-Based Delayed List Scheduling Is a (1 + β)(1 + 1/β + max{1, (m − 1)Δ/m})-Approximation for P|r_j, prec|E[Σ w_j C_j]Research Paper

Scheduling jobs whose processing times are not known in advance is a basic problem of production planning, project management and computing systems. In the stochastic machine scheduling model only the distribution of each processing time is known beforehand; the actual duration of a job is revealed when the job completes. A solution is then not a schedule…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem: The Integer Points of P1 ∩ P2 Are Exactly the CVRP Solutions, and the Dantzig–Wolfe Master Describes P1 ∩ P2Research Paper

The capacitated vehicle routing problem (CVRP) asks for KKK delivery routes from a depot that serve every client exactly once without exceeding a vehicle capacity, at minimum total length. It was introduced by Dantzig and Ramser in 1959 and is the reference problem of the vehicle routing literature: most exact methods for richer routing models (time windows,…

17 thms3 active usersReviewed
🏆Completed
Complexity TheoryOperations ResearchOptimization·Captain: mikedeng1

On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming 2: The Adaptive-Step Algorithm in N∞(β) or N∞⁻(β) with γ ≤ 2(1 − β) Attains Precision t in O(nt) IterationsResearch Paper

Primal-dual interior-point methods solve a linear program by following, approximately, the central path of strictly feasible primal-dual pairs whose complementarity products xjsjx_js_jxj​sj​ are all equal. Every such method confines its iterates to a neighbourhood of that path, and the neighbourhood governs both the theory and the practice. The first primal-dual…

11 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Scheduling Unrelated Parallel Machines 2: Enumerating Long Assignments and Rounding the LP Gives a (1 + ε)-Approximation for MakespanResearch Paper

Scheduling independent jobs on unrelated parallel machines to minimize the makespan is one of the basic NP-hard problems of scheduling theory: each job has its own processing time on each machine, with no relation between machines, and the goal is to finish all jobs as early as possible. When the number of machines is part of the input, Lenstra, Shmoys and…

10 thms3 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms III: Every Directed Uniform Multicommodity Flow Problem Has Ω(𝒮/log n) ≤ f ≤ 𝒮Research Paper

Many graph problems in routing, VLSI layout and scheduling ask for a cut that separates a lot of demand while cutting little capacity. For a single commodity, the max-flow min-cut theorem of Ford and Fulkerson says that the largest flow equals the smallest cut. For several commodities sharing one network this equality fails, and the question becomes how far…

8 thms3 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms II: Every Product Multicommodity Flow Problem with k Commodities Has Ω(𝒮/log k) ≤ f ≤ 𝒮Research Paper

For a single commodity, the Ford–Fulkerson theorem says that the maximum flow between two nodes equals the minimum capacity of a cut separating them. Many routing and partitioning problems involve many source–sink pairs at once, and for those the equality fails: the largest fraction of every demand that can be routed simultaneously can be strictly smaller…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

Linear Programming and Markov Decision Chains 2: Representatives of Average Optimal Stationary Policies Are Optimal Dual Solutions, and Every Optimal Dual Solution Gives an Average Optimal PolicyResearch Paper

A finite Markov decision process may have several recurrent classes under one policy. In that setting, its long-run reward depends on the initial state, and a single stationary distribution does not describe the whole decision problem. Hordijk and Kallenberg developed a linear program with two families of variables to handle this multichain case. Their…

13 thms3 active usersReviewed
PreviousPage 7 of 15Next

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