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 ResearchOptimization·Captain: mikedeng1

Revenue Management Under the Markov Chain Choice Model I: The Dual Linear Program Yields an Optimal AssortmentResearch Paper

A retailer or an airline decides which products to make available, and customers choose among what is offered. When a preferred product is missing, many customers substitute to another product instead of leaving. Assortment optimization asks which subset of products to offer so that the expected revenue from a customer is as large as possible, and its…

11 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis II: Local Optimality for Integrally Convex FunctionsTextbook

For a convex function on Rn\mathbb R^nRn, a point is a global minimizer as soon as it is a local minimizer — this is one of the earliest and most consequential facts of convex analysis, and it underlies why local-search and gradient methods can certify global optimality in convex programs. The discrete analogue is not automatic: a function on the integer…

14 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research·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 OptimizationOperations ResearchOptimization·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
Discrete GeometryOperations ResearchOptimization·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
Machine LearningOperations ResearchOptimal 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 OptimizationOperations ResearchOptimization·Captain: mikedeng1

Validation of Subgradient Optimization I: The Core Problem Built from the Subgradient Iterates Solves the Dual Linear ProgramResearch Paper

Subgradient optimization maximizes a concave function that is not differentiable by stepping along an arbitrary subgradient with a prescribed sequence of step sizes. It became a standard tool of integer programming after Held and Karp used it to compute the Lagrangian 1-tree bound for the traveling-salesman problem (Held & Karp 1971). Held, Wolfe and…

7 thms2 active usersReviewed
🏆Completed
Discrete GeometryOperations ResearchOptimization·Captain: mikedeng1

Elementare Theorie der konvexen Polyeder I: A Point on All Extreme Supports of a Finite Cone Is a Nonnegative Combination of at Most n GeneratorsResearch Paper

A polyhedral cone can be described in two ways: as the set of nonnegative combinations of finitely many vectors (a finitely generated cone), or as the intersection of finitely many closed half-spaces through the origin. That the two descriptions give the same class of sets is the Minkowski–Weyl theorem. It is the structural basis of linear programming: the…

9 thms2 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities I: Fisher Markets with an Equilibrium Have Rational Equilibrium Prices of Polynomial Bit SizeResearch Paper

A Fisher market is the simplest model of a market in which prices are set by supply and demand: buyers bring money, sellers bring goods, and a price vector is an equilibrium when every buyer, spending her money optimally at those prices, leaves every good exactly sold out. Computing equilibria is one of the central questions of algorithmic game theory,…

8 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraOperations Research+1·Captain: mikedeng1

Path-Finding Methods for Linear Programming II: Properties of the Regularized D-Optimal-Design Weight FunctionResearch Paper

Interior point methods for a linear program min⁡{c⊤x:Ax≥b}\min\{c^\top x : Ax\ge b\}min{c⊤x:Ax≥b} with A∈Rm×nA\in\mathbb R^{m\times n}A∈Rm×n follow the central path of the logarithmic barrier −∑ilog⁡si-\sum_i\log s_i−∑i​logsi​, where s=Ax−bs=Ax-bs=Ax−b is the slack vector. Renegar's path-following analysis (1988) gives O(m L)O(\sqrt m\,L)O(m​L) iterations, and for decades this was the best bound for methods whose iterations cost a linear…

7 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Path-Finding Methods for Linear Programming I: Centering with Weights on the Weighted Central PathResearch Paper

Interior point methods solve a linear program by following a central path: a curve of minimizers of a penalized objective that trades off cost against distance from the boundary of the feasible region. The classical analysis of path following with the logarithmic barrier needs O(m L)O(\sqrt{m}\,L)O(m​L) iterations for a program with mmm constraints, where LLL is the bit…

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

Critical-Path Planning and Scheduling II: The Project Cost Curve Is Non-Increasing, Piecewise Linear and ConvexResearch Paper

A large engineering or construction project is a set of jobs with precedence constraints, and most jobs can be finished faster at a higher cost (overtime, more crews, faster equipment). Planners want to know, for every possible project duration, the cheapest way to meet it. The resulting trade-off between duration and direct cost is what management compares…

10 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Finding Minimum-Cost Circulations by Canceling Negative Cycles: Polynomial Termination of Minimum-Mean Cycle CancelingResearch Paper

The minimum-cost circulation problem is a central problem of network optimization: transportation, assignment, shortest-path and maximum-flow problems are all special cases, and it is one of the few classes of linear programs with fast combinatorial algorithms. The oldest algorithm for it, the cycle-canceling algorithm of Klein (1967), repeatedly finds a…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research·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 TheoryOperations Research·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 TheoryOperations Research·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
CombinatoricsDiscrete GeometryOperations Research·Captain: mikedeng1

On Sub-determinants and the Diameter of Polyhedra: A Polynomial Diameter Bound in the Largest SubdeterminantResearch Paper

The combinatorial diameter of a polyhedron is the largest distance, in its vertex-edge graph, between two vertices. It is a lower bound on the number of pivots any edge-following method such as the simplex method needs in the worst case, which is why the polynomial Hirsch conjecture — the diameter of P={x∈Rn:Ax≤b}P = \{x \in \mathbb{R}^n : Ax \le b\}P={x∈Rn:Ax≤b} is bounded by a…

11 thms2 active usersReviewed
🏆Completed
Stochastic Systems·Captain: mikedeng1

Stochastic Linear Programming 02: Finiteness and Smoothness of Expected Fixed RecourseTextbook

A two-stage stochastic linear program chooses a first-stage decision before uncertain coefficients are known and then uses recourse variables to repair the decision after the data are observed. The resulting expected recourse cost is central to existence, stability, and numerical methods: if it can be infinite, an apparently feasible model may still have no…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical 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
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Introduction to Stochastic Programming V: The Integer L-Shaped MethodTextbook

Two-stage stochastic programs with recourse are already hard to optimize when the recourse problem is a linear program: Chapters 4–6 of this series show how the L-shaped method exploits the recourse function's convexity and polyhedrality to converge finitely by cutting planes. Adding integrality restrictions destroys both properties. Birge and Louveaux open…

6 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Introduction to Stochastic Programming IV: Nested Decomposition for Multistage ProgramsTextbook

Sequential planning problems — inventory replenishment, hydro-thermal power scheduling, asset-liability management — routinely span more than two decision epochs, with information about the future revealed gradually as each period unfolds. A two-stage recourse model (decide now, observe once, recourse once) is too coarse for these: it either collapses the…

6 thms2 active users
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Introduction to Linear Optimization VI: Farkas' Lemma and Separating HyperplanesTextbook

When is a system of linear constraints infeasible? Sections 4.6-4.7 of Bertsimas-Tsitsiklis answer with the archetypal theorem of the alternative. The capstone is Farkas' lemma (Theorem 4.6): for an m×nm \times nm×n matrix AAA and b∈Rmb \in \mathbb{R}^mb∈Rm, exactly one of the following holds — (a) some x≥0x \ge 0x≥0 satisfies Ax=bAx = bAx=b, or (b) some ppp satisfies p′A≥0′p'A \ge 0'p′A≥0′ and …

8 thms2 active usersReviewed
🏆Completed
Optimization·Captain: Shuze Chen

Introduction to Linear Optimization III: Fourier–Motzkin Elimination and Projections of PolyhedraTextbook

Is the shadow of a polyhedron again a polyhedron? §2.8 of Bertsimas–Tsitsiklis answers this with perhaps the oldest method for solving linear programming problems: Fourier–Motzkin elimination. Given P={x∈Rn∣∑j=1naijxj≥bi, i=1,…,m}P = \{x \in \mathbb{R}^n \mid \sum_{j=1}^n a_{ij}x_j \ge b_i,\ i = 1, \dots, m\}P={x∈Rn∣∑j=1n​aij​xj​≥bi​, i=1,…,m}, one sorts the constraints by the sign of the coefficient of xnx_nxn​ — rewriting…

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

Introduction to Linear Optimization II: Existence and Optimality of Extreme PointsTextbook

Where should one look for the optimum of a linear programming problem? Chapter 1 of Bertsimas–Tsitsiklis suggests that optima "tend to occur at corners" of the feasible polyhedron; §§2.5–2.6 turn this intuition into theorems. Not every polyhedron has a corner — a halfspace in Rn\mathbb{R}^nRn (n>1n > 1n>1) has none — and the exact dividing line is the presence of an…

12 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: hypercube

Approximate Dual Separation for the Cluster LP: a 1.3871.3871.387-approximation for Correlation ClusteringResearch Paper

Suppose every pair of vertices comes with a positive or negative judgment. A partition agrees with a positive judgment when the vertices lie in the same block and with a negative judgment when they lie in different blocks. MinDisagree asks for a partition with as few disagreements as possible. The number of blocks is unrestricted. This mission concerns…

29 thms1 active userReviewed
PreviousPage 18 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