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
Operations ResearchProbabilityStatistics·Captain: iris

Rank-One Boolean Tensor Factorization and the Multilinear Polytope: The Flower LP Recovers the Planted Rank-One Tensor w.h.p. Under Semi-Random Corruption When p<rw/(1+2rw)p < r_w/(1 + 2r_w)p<rw​/(1+2rw​)Research Paper

Boolean tensor factorization writes a binary data tensor as a Boolean combination of a few binary rank-one tensors. It is used in data mining for binary relational data (subject–relation–object triples, user–item–context records) and in latent-structure discovery, where the factors are read directly as sets of rows, columns and slices. Even its rank-one…

26 thms3 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: iris

Understanding the Value of Fulfillment Flexibility in an Online Retailing Environment: A Spillover Limit Policy Costs at Most (1+O(T−1/2))(1 + O(T^{-1/2}))(1+O(T−1/2)) Times the DLP Lower BoundResearch Paper

An online retailer stores each product in several distribution centers (DCs) and tries to ship every order from the DC next to the customer. When that DC has run out, the order can often be shipped from another DC, at a higher cost and with a longer delivery time, and some customers then walk away. Allowing such spillover is the fulfillment flexibility of…

17 thms3 active usersReviewed
Operations ResearchProbability·Captain: iris

An Improved Analysis of LP-based Control for Revenue Management: Horizon-Independent Regret of the Re-Solving Algorithm Under NondegeneracyResearch Paper

In network revenue management and online linear programming, orders arrive one per period over a horizon of TTT periods. Each order requests a bundle of mmm resources and offers a reward. The decision maker accepts or rejects it at once and irrevocably, without exceeding the stock of each resource. Airline seat allocation, hotel booking and ad allocation are…

25 thms3 active usersReviewed
CombinatoricsConvex OptimizationOptimization·Captain: iris

On Polyhedral Approximations of the Positive Semidefinite Cone: Every Polytope Between (1−ε)(D − A) and D − A Has Extension Complexity at Least exp(c√n)Research Paper

Linear programs are the workhorse of optimization, and a recurring question is which convex sets can be described, or approximated, by a linear program of small size. The relevant measure is the extension complexity xc⁡(P)\operatorname{xc}(P)xc(P) of a polytope PPP: the smallest number of facets of a polytope that projects linearly onto PPP. If xc⁡(P)=N\operatorname{xc}(P)=Nxc(P)=N,…

26 thms3 active usersReviewed
🏆Completed
CombinatoricsDiscrete Geometry·Captain: iris

Combinatorial Optimization (Cook et al.) XIV: Edmonds' Matroid Intersection Polytope TheoremTextbook

Many combinatorial optimization problems ask for a maximum-weight set that is "independent" in two different senses at once: a bipartite matching is a set of edges that uses each left node at most once and each right node at most once; a branching in a digraph is a forest that enters each node at most once. Each of these is a common independent set of two…

27 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation XII: aggregating a stagewise independent multistage program gives a lower bound that refining never decreasesTextbook

A multi-stage stochastic linear program chooses decisions over TTT stages while a random process unfolds, each decision depending only on what has been observed so far. Such problems arise in planning under uncertainty, from production and energy systems to asset-liability management. With a non-discrete distribution the unknowns are functions, and the…

48 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: iris

Combinatorial Optimization (Cook et al.) XI: The Subtour Bound Equals the Optimal Held–Karp Bound (corrected: loopless)Textbook

The traveling salesman problem (TSP) asks for a cheapest circuit through every node of a graph with edge costs. No polynomial-time algorithm is known, and exact codes for large instances depend on strong lower bounds to prune their search. Two lower bounds dominate the classical literature. The first is the subtour bound, the optimal value of the linear…

27 thms3 active usersReviewed
Operations ResearchOptimization·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation X: multiple simple recourse reduces to simple recourse with a mixed distributionTextbook

In a two-stage stochastic linear program, a simple recourse constraint penalizes the gap between a first-stage quantity zzz (for example a production level tTxt^{\mathrm T}xtTx) and a random demand ξ~\tilde\xiξ~​ at constant unit costs: a surplus z>ξ~z>\tilde\xiz>ξ~​ costs β\betaβ per unit and a shortage z<ξ~z<\tilde\xiz<ξ~​ costs α\alphaα per unit. Its expected cost has a closed form in the…

21 thms3 active usersReviewed
🏆Completed
CombinatoricsOptimization·Captain: iris

Combinatorial Optimization (Cook et al.) XII: Edmonds' Matroid Polytope TheoremTextbook

The Greedy Algorithm builds a set one element at a time, always adding the heaviest element that keeps the set feasible. For the forests of a graph it finds a maximum-weight forest (Kruskal's algorithm), but for the matchings of a graph it can fail: on a 4-cycle with edge weights 9, 7, 8, 3 it picks the edges of weight 9 and 3 when the edges of weight 7 and…

21 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: iris

Combinatorial Optimization (Cook et al.) I: The Characteristic Vector of a Minimum Spanning Tree Is an Optimal Solution of the Spanning-Tree Linear ProgramTextbook

A minimum spanning tree (MST) of a connected graph with edge costs is a cheapest set of edges that connects all nodes and contains no circuit. It is the prototype of a combinatorial optimization problem solved exactly by a greedy rule, and it opens Chapter 2 of Cook, Cunningham, Pulleyblank and Schrijver's Combinatorial Optimization (Wiley, 1998). The…

21 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: iris

Combinatorial Optimization (Cook et al.) VII: For Arbitrary Costs the Minimum Cost of a T-Join Equals the Optimal Value of Its Linear ProgramTextbook

A mail carrier must walk every street of a district and return to the post office, and wants to walk as little as possible. Kwan Mei-Ko posed this Chinese postman problem in 1962. Edmonds observed that the extra streets to be walked a second time form a set of edges whose odd-degree nodes are exactly the odd-degree nodes of the street graph, and generalized…

25 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear algebra·Captain: iris

Combinatorial Optimization (Cook et al.) IX: The Hoffman–Kruskal Theorem: {x≥0:Ax≤b}\{x \ge 0 : Ax \le b\}{x≥0:Ax≤b} Is Integral for All Integral bbb Iff AAA Is Totally UnimodularTextbook

Many combinatorial optimization problems (bipartite matching, maximum flow, shortest paths, transportation and assignment problems) can be written as integer programs

10 thms3 active usersReviewed
Algorithmic Game TheoryCombinatorics·Captain: iris

Popularity, Mixed Matchings, and Self-duality: every bipartite instance with strict preferences has a max-utility popular mixed matching {(M0,1/2),(M1,1/2)}, pure if a stable matching is perfectResearch Paper

In a two-sided matching market, applicants and jobs rank their acceptable partners, and a planner wants an assignment that is both acceptable to the participants and good for some external objective, such as total value. Stability (no applicant–job pair prefers each other to their assignments) is the classical acceptability notion, but it is restrictive:…

24 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Adjustable Robust Optimization Reformulations of Two-Stage Worst-Case Regret Minimization Problems: Exact reformulation of absolute regret with objective uncertaintyResearch Paper

A planner who commits resources before learning their eventual returns can evaluate a decision by how much better another decision would have performed after those returns became known. This absolute regret criterion compares against the best feasible hindsight decision under the same realization of uncertainty. It differs from protecting only the lowest…

6 thms3 active usersReviewed
🏆Completed
OptimizationProbability·Captain: Shuze Chen

The Price of Robustness: Tight probability bounds for symmetric uncertaintyResearch Paper

A linear optimization model can prescribe a decision that uses nearly all available capacity. If the coefficients measuring resource consumption are uncertain, even a small change can make that decision infeasible. Protecting against every simultaneous adverse change can instead sacrifice a substantial amount of the nominal objective. Budgeted robustness int…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Production Planning by Mixed Integer Programming V: Intersecting Constant-Capacity Lot-Sizing HullsTextbook

A production plan must meet demand on time while deciding which periods justify a setup. When each active period can supply at most the same amount, the capacity limit links setup decisions to cumulative demand. A linear relaxation that treats those decisions as fractional may admit plans that cannot be assembled from feasible binary setup schedules.…

6 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Production Planning by Mixed Integer Programming III: The Wagner–Whitin Convex HullTextbook

A production planner must meet demand over several periods while deciding when to incur fixed setup costs. Producing early can combine several periods into one batch, but the resulting inventory carries a holding cost. Even for one item without a capacity limit, continuous production quantities interact with discrete setup decisions. An exact linear…

6 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Production Planning by Mixed Integer Programming I: Facility Location Reformulation of Uncapacitated Lot-SizingTextbook

Production planning combines continuous quantities with discrete decisions about when a machine is prepared to produce. A setup can incur a fixed charge even when the amount subsequently produced is small. Relaxing the setup decision to a fraction can therefore give a cost bound that is too optimistic. For a single product without capacity limits, a…

4 thms3 active usersReviewed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Improved Guarantees for the A Priori TSP: Random Sampling with Probability 1 − (1 − p)^0.663 and a 3/2-Approximate Master Tour Has Approximation Guarantee Below 3.1 on Instances with a DepotResearch Paper

In the a priori traveling salesman problem with independent activation, a tour through all customers must be fixed before it is known which customers need a visit; each customer is active independently with a known probability, and the fixed tour is afterwards cut short to the active ones. The model, introduced by Jaillet and by Bertsimas as the…

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

Revenue Management with Repeated Customer Interactions: the myopic policy earns at least a (1 − γ) fraction of the optimal revenue under bang-per-buck heterogeneity γResearch Paper

Network revenue management studies how a platform with limited supply should allocate products to customers at given prices. Most of the literature treats each interaction as one-shot: a request arrives, is served or rejected, and leaves. Examples are the fluid models of Gallego and van Ryzin (1997) and the bid-price controls of Talluri and van Ryzin (1998).…

13 thms3 active usersReviewed
CombinatoricsOperations Research·Captain: mikedeng1

A Discrete Convex Min-Max Formula for Box-TDI Polyhedra: Min-Max Theorem for Separable Discrete Convex Functions over Integral Points of a Box-TDI PolyhedronResearch Paper

Minimizing a separable convex function over the integral points of a polyhedron is a recurring problem in combinatorial optimization: resource allocation, minimum-cost flows with convex costs, and the "fair" or "decreasingly minimal" integral elements studied by Frank and Murota all have this form. When the polyhedron is described by a totally unimodular…

17 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Joint Product Framing (Display, Ranking, Pricing) and Order Fulfillment Under the Multinomial Logit Model for E-Commerce Retailers: Randomized Framing and Fulfillment Loses O(√θ) Against DET'Research Paper

An online retailer decides, for every arriving customer, how to frame its catalog: which products are displayed, in which section or position, and at which of several price points. Framing changes demand. A product on a promotional banner sells more than the same product further down the page. The retailer must also decide which fulfillment center (FC)…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsDiscrete GeometryOperations Research+1·Captain: mikedeng1

Binary Extended Formulations and Sequential Convexification: Among All d-Hypercube Binarizations, the Logarithmic Binarization Has Minimum RankResearch Paper

Mixed-integer programs often contain general integer variables x∈{0,…,k}x \in \{0, \dots, k\}x∈{0,…,k}. A standard modelling device replaces such a variable by ddd binary variables y∈{0,1}dy \in \{0,1\}^dy∈{0,1}d linked to xxx through a polytope, a binarization. Examples are the unary encoding, the "full" encoding with one indicator per value, and the logarithmic encoding x=∑i2i−1yix = \sum_i 2^{i-1} y_ix=∑i​2i−1yi​.…

15 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: Shuze Chen

Modeling, Measuring and Managing Risk X: Dual Representation of Polyhedral Acceptability FunctionalsTextbook

Risk measures enter optimization models as objectives or constraints, and the models that use them most, multi-stage stochastic programs, are solved as large linear programs. A risk functional is only usable there if it can itself be written as the value of a linear program. Eichhorn and Römisch introduced polyhedral risk measures for this purpose (doi:10.11…

9 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: mikedeng1

Network Inspection for Detecting Strategic Attacks: The Equilibrium Detection Rate and Inspection Strategies Do Not Depend on the Attacker's Number of ResourcesResearch Paper

Utility networks such as water pipelines, gas distribution systems and power grids are exposed to attacks on their physical components. An operator who cannot monitor every component must decide where to place a limited number of detectors, without knowing which components an adversary will target or how many of them. Dahan, Sela and Amin (arXiv:1705.00349,…

11 thms3 active usersReviewed
PreviousPage 7 of 19Next

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