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

On the Power and Limitations of Affine Policies in Two-Stage Adaptive Optimization II: With m + 3 Extreme Points the Best Affine Policy Can Cost More Than (2 − δ) Times the OptimumResearch Paper

Two-stage adaptive optimization models decisions made in two steps: a first-stage decision is fixed before an uncertain parameter is revealed, and a second-stage (recourse) decision may then depend on the realized value. In the robust version, the uncertain parameter ranges over an uncertainty set and the objective is the worst-case cost. Such models arise…

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

On the Power and Limitations of Affine Policies in Two-Stage Adaptive Optimization I: An Affine Policy Is Optimal When the Uncertainty Set Is a SimplexResearch Paper

Two-stage adaptive optimization models decisions taken in two rounds: a first-stage decision xxx is fixed before an uncertain parameter is revealed, and a second-stage decision y(b)y(b)y(b) is chosen after the parameter bbb is observed, so that the second stage may depend on bbb arbitrarily. The objective is the worst case over an uncertainty set U\mathcal UU of possible…

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

Maximization of a Linear Function of Variables Subject to Linear Inequalities: Under Nondegeneracy the Simplex Technique Ends in Infeasibility, Unboundedness, or a Maximum Feasible SolutionResearch Paper

Linear programming asks for the best value of a linear objective under linear constraints. In the form studied by George B. Dantzig in 1951, all variables are nonnegative and the constraints are equalities. The simplex technique moves between small sets of columns, seeking a feasible vector first and then improving its objective. Its basic promise is…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Maximum Matching and a Polyhedron With 0,1-Vertices: The Vertices of the Matching Polyhedron Are Exactly the Matching VectorsResearch Paper

A matching in a graph is a set of edges no two of which share a node. Given a real weight on every edge, the maximum-weight matching problem asks for a matching of largest total weight. It is one of the basic problems of combinatorial optimization: assignment, pairing and scheduling problems reduce to it, and it is the standard example of a combinatorial…

13 thms4 active usersReviewed
🏆Completed
Discrete GeometryOperations ResearchOptimization+1·Captain: mikedeng1

Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time 1: The Expected Shadow of a Gaussian-Perturbed Polytope Has Polynomially Many VerticesResearch Paper

The simplex method solves linear programs very fast in practice, yet for most pivot rules there are inputs on which it takes exponentially many steps (Klee and Minty, 1972, for Dantzig's rule; Goldfarb, 1983, for the shadow-vertex rule). Average-case analyses (Borgwardt, 1980s; Smale, 1983) explained good behaviour on random inputs, but random inputs look…

31 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

On Sequential Decisions and Markov Chains 2: Under Irreducibility, an Optimal Solution of a Linear Program over State-Action Frequencies Yields an Optimal Stationary ProcedureResearch Paper

A Markov decision problem asks how to control a system that moves at random between finitely many states, where each decision changes the probabilities of the next move and incurs a cost. Cyrus Derman's 1962 paper On Sequential Decisions and Markov Chains (Management Science 9(1):16–24) treats two criteria: the long-run average cost per period, and the total…

11 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Air Travel Demand and Airline Seat Inventory Management I: Marginal Seat Allocation Among Distinct Fare ClassesTextbook

An airline sells the seats of one flight leg at several prices. Low fares fill seats that would otherwise fly empty; high fares are bought by passengers who book late and cannot be predicted exactly. Seat inventory control decides how many seats each fare class may sell. Peter Belobaba's 1987 MIT dissertation (MIT Flight Transportation Laboratory Report…

8 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Real-Time Optimization of Personalized Assortments: Inventory Balancing Is α_cmin(Ψ)-CompetitiveResearch Paper

Online retailers choose, customer by customer, which products to display. The customer's type (location, history, device) is revealed on arrival. Inventories are finite and are not replenished during the selling season. A seller who shows every customer the currently most profitable products can sell out a product early and leave nothing for later customers…

14 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

A Dynamic Near-Optimal Algorithm for Online Linear Programming II: A Lower Bound for Every Online AlgorithmResearch Paper

Online linear programming models resource allocation under uncertainty about future demand: requests arrive one at a time, each asking for some amounts of mmm resources and offering a payment, and each must be accepted or rejected, irrevocably, on arrival. Airline seat and hotel room revenue management, online routing with bandwidth limits and the allocation…

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

Linear Programming: Foundations and Extensions I: Degeneracy and Termination of the Simplex Method under Bland's RuleTextbook

The simplex method is the standard algorithm for linear programming, and its correctness rests on one question: does it stop? Each pivot of the method moves from one dictionary to another without decreasing the objective value, but a pivot can leave the objective unchanged. When that happens repeatedly, the method can return to a dictionary it has already…

10 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOperations Research·Captain: mikedeng1

Theory of Games and Economic Behavior III: Mixed Strategies, the Minimax Theorem and Good StrategiesTextbook

A zero-sum two-person game in normalized form is a real matrix H(τ1,τ2)\mathcal H(\tau_1, \tau_2)H(τ1​,τ2​): player 1 chooses a row τ1\tau_1τ1​, player 2 simultaneously chooses a column τ2\tau_2τ2​, and player 2 pays player 1 the amount H(τ1,τ2)\mathcal H(\tau_1, \tau_2)H(τ1​,τ2​). Matrix games are the base case of non-cooperative game theory, the prototype of every minimax statement in optimization,…

11 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Numerical Techniques for Stochastic Optimization I: Edmundson–Madansky Bounds for Independent Random Data and Simple RecourseTextbook

In a two-stage stochastic linear program a decision xxx is taken before random data ξ\xiξ are observed, and a corrective recourse decision yyy is taken afterwards at a cost. The objective contains the expectation of an optimal value of a linear program, ∫Q(x,ξ(ω)) P(dω)\int Q(x,\xi(\omega))\,P(d\omega)∫Q(x,ξ(ω))P(dω), and for continuous or high-dimensional ξ\xiξ that integral cannot be evaluated…

13 thms4 active usersReviewed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

The Matroids with the Max-Flow Min-Cut Property: Binary Mengerian Clutters and the Q6 MinorResearch Paper

Several classical theorems of combinatorial optimization say that a family of sets arising from a graph packs: the maximum number of pairwise disjoint members equals the minimum size of a set meeting every member. König's theorem on bipartite graphs, Menger's theorem, the max-flow min-cut theorem of Ford and Fulkerson, Edmonds' branching theorem and the…

30 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Selected Topics in Column Generation III: Ryan–Foster Branching — a Fractional Basic Set-Partitioning Solution Covers Some Row Pair FractionallyResearch Paper

Column generation solves linear programs with far too many variables to list: one works with a small subset J′⊆JJ' \subseteq JJ′⊆J of the columns, the restricted master problem (RMP), and adds columns of negative reduced cost as a pricing problem finds them (Lübbecke and Desrosiers 2005, §2.1). Many integer programs from vehicle routing, crew scheduling and crew…

5 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Competitive Randomized Algorithms for Nonuniform Problems IV: The Optimal Randomized Two-Server Ratio 1652/1069 on the 3-4-5 TriangleResearch Paper

The kkk-server problem is a basic model of on-line decision making. kkk mobile servers move in a metric space, requests for points arrive one at a time, and each request has to be covered by a server before the next one arrives. The cost is the total distance the servers move. The problem includes paging, caching and disk-head scheduling as special cases (Manass…

7 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Competitive Randomized Algorithms for Nonuniform Problems I: Optimal Competitiveness of Randomized Block Snoopy CachingResearch Paper

In a shared-memory multiprocessor, each processor keeps copies of memory blocks in its own cache, and all caches listen ("snoop") on a common bus. Every bus cycle spent keeping these copies consistent is a cycle not available for useful work, so the protocol that decides when a block is shared by several caches and when it is private to one cache directly…

8 thms4 active usersReviewed
🏆Completed
Discrete GeometryOperations ResearchOptimization·Captain: mikedeng1

Elementare Theorie der konvexen Polyeder II: Finitely Many Linear Inequalities Define a Convex Polytope Iff Their Normals Positively Span and the Region Has an Interior PointResearch Paper

A convex polytope has two standard descriptions: as the convex hull of finitely many points, and as the intersection of finitely many half-spaces. Linear programming uses both at once. The feasible region of a linear program is given by inequalities, while the simplex method and the theory of basic solutions work with its vertices. That the two descriptions…

14 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Robust solutions of Linear Programming problems contaminated with uncertain data: A Violation-Probability Bound for the Robust CounterpartResearch Paper

Linear programs solved in practice carry data that are measured, estimated or rounded. Ben-Tal and Nemirovski (Math. Program. 88, 2000) examined the NETLIB collection of real-world LPs and found that in 13 of them a relative perturbation of only 0.01% in the "ugly" coefficients of the inequality constraints can make the nominal optimal solution more than…

12 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

The Assignment Game I: The Core 2: The High-Price and Low-Price Corners of the CoreResearch Paper

A two-sided market in which each seller owns one indivisible good (a house, in the paper's example) and each buyer wants at most one is the simplest model in which prices emerge from bargaining between individuals rather than from a supply curve. Shapley and Shubik, The Assignment Game I: The Core (Int. J. Game Theory 1 (1971)), treat this market as a…

7 thms4 active usersReviewed
🏆Completed
Discrete GeometryNumber TheoryOperations Research+1·Captain: mikedeng1

Maximal Lattice-Free Convex Sets in Linear Subspaces I: Characterization of Maximal Lattice-Free Convex Sets in a SubspaceResearch Paper

Cutting planes for mixed-integer linear programs are often derived from convex sets that contain no integer point in their interior. Balas observed in 1971 that every such lattice-free convex set containing the current fractional LP solution in its interior yields a valid inequality, the intersection cut (Balas, Intersection cuts, Oper. Res. 19, 1971). The…

18 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: Shuze Chen

Disjunctive Programming XVI: Unions of Upper Monotone Polytopes and PolymatroidsTextbook

This mission is the sixteenth and last of the Disjunctive Programming series, and its goal theorem is the book's own closing result. The chapter's arc closes a loop opened at the very start of the book: Theorem 2.1 (02a-convex-hull) gave the convex hull of a union of polyhedra in the same space via lifting; this chapter's Theorem 13.13 (not drafted in this…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: Shuze Chen

Disjunctive Programming XV: Dominants of Polytopes and Upper SeparationTextbook

Many real-world disjunctive models are not unions of polyhedra in a single shared space, but unions of polyhedra in different spaces linked by a logical implication: some action affecting one set of entities has consequences for another. Balas's treatment of such models (§17 of the book, following [17]) reduces to understanding a single auxiliary object…

8 thms4 active users
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Disjunctive Programming XIV: Disjunctive Cuts from the V-Polyhedral RepresentationTextbook

The lift-and-project cut-generating LP (CGLP) is the workhorse of the book's cutting-plane machinery, but its number of variables grows with qqq, the number of terms in the disjunction — a real computational cost for disjunctions with many terms. An alternative representation of the same disjunctive hull, built from vertices and extreme rays rather than from…

7 thms4 active users
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Disjunctive Programming XIII: Monoidal Cut Strengthening and the Gomory Mixed-Integer CutTextbook

The Gomory mixed-integer (GMI) cut is the single most widely deployed cutting plane in practical mixed-integer programming: every commercial solver generates it, from a simplex tableau row, essentially for free. Yet the GMI cut is not the strongest cut derivable from the same row: once a subset of the variables is known to be integer-constrained, that…

8 thms4 active users
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Disjunctive Programming XI: The Cut-Generating LP Under a Ray NormalizationTextbook

Lift-and-project (L&P) cuts strengthen the linear relaxation of a mixed 0-1 program by separating a fractional point from the convex hull of a disjunction such as xk≤0∨xk≥1x_k \le 0 \lor x_k \ge 1xk​≤0∨xk​≥1. Generating an optimal L&P cut means solving the cut-generating linear program (CGLP), a linear program lifted to a space with one new pair of variables per constraint of…

8 thms4 active usersReviewed
PreviousPage 5 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