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 ResearchOptimizationProbability+1·Captain: mikedeng1

On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming 4: For a Random Subspace, ‖Pq‖⁻∞ ≤ (log n/n)‖r‖² with Probability Tending to OneResearch Paper

Primal–dual interior point methods follow a path of strictly feasible solutions to a linear program. Their worst case iteration bounds come from controlling a term that is quadratic in each search step. Mizuno, Todd, and Ye asked whether that term is typically much smaller than its worst case bound under a model in which a certain subspace is randomly…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

Integer Programming Formulation of Traveling Salesman Problems: The Miller–Tucker–Zemlin Constraints Exactly Describe the Itineraries with at Most p Cities per TourResearch Paper

The traveling salesman problem asks for a shortest closed route through a set of cities. Writing it as an integer program requires linear constraints whose integer solutions are exactly the routes. The assignment constraints (each city entered once and left once) are not enough: their integer solutions include collections of disjoint cycles, called subtours,…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

On the Job-Shop Scheduling Problem: The Integer Program (2)–(7) with 0–1 Variables y_jk Attains Exactly the Minimum Make-SpanResearch Paper

The job-shop scheduling problem asks how to time a set of tasks on shared machines so that every product is finished as early as possible. Around 1959 several authors proposed to solve it with Gomory's then new integer programming (Gomory 1958). The obstacle is the noninterference condition: two tasks on the same machine must not overlap, so one of them…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Approximation Algorithms for Scheduling Unrelated Parallel Machines 1: Binary Search over Rounded LP Vertices Finds a Schedule within Twice the Optimal MakespanResearch Paper

Scheduling unrelated parallel machines to minimize the makespan, written R ∥ Cmax⁡R\,\|\,C_{\max}R∥Cmax​, is one of the basic NP-hard problems of scheduling theory. A set of jobs must each be run on one of several machines, and the time a job takes depends arbitrarily on the machine; the goal is to finish all jobs as early as possible. Before the work formalized here, the…

11 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Algorithms for the Assignment and Transportation Problems: Munkres' Algorithm Terminates on Every Real n × n Matrix, and Its Final Starred Zeros Form a Minimum-Sum AssignmentResearch Paper

The assignment problem asks how to assign nnn men to nnn jobs, one man per job, so that the total cost (or, equivalently, the total rating) is optimal. It is the simplest combinatorial optimization problem with a nontrivial polynomial-time algorithm, and it appears as a subroutine across operations research: in transportation and network-flow methods, in…

15 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems IV: Positive Dynamic Programming — an Extreme Optimal Dual Solution Yields a Pure Stationary Optimal PolicyTextbook

A finite Markov decision system asks how to choose actions while a changing state controls which actions are available. The choice can affect both the reward now and the distribution of future states. In a total-reward problem, the process can continue indefinitely; if transitions are substochastic, it can also terminate. Kallenberg's treatment of positive…

6 thms2 active usersReviewed
🏆Completed
Discrete GeometryGroup Theory·Captain: mikedeng1

Some Polyhedra Related to Combinatorial Problems II: The Faces of the Master Polyhedron P(G, g0) Are the Basic Feasible Solutions of a Subadditive Linear SystemResearch Paper

Finite group equations arise when an integer program is expressed relative to an integer basis: the residue of a candidate solution in a finite Abelian group records whether it satisfies the original integrality requirement. Gomory's group polyhedron collects the nonnegative integer solutions with one prescribed residue. Its faces give valid linear…

11 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization+2·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems IX: Discounted Semi-Markov Decision Processes — the Value Vector Is the Smallest Superharmonic VectorTextbook

A decision maker may choose an action whenever a system changes state, even though the time until the next change is random. Maintenance and replacement decisions are examples: a repair choice changes both the next operating state and the length of time before another choice is available. A discrete-time Markov decision model gives every decision epoch the…

6 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Some Polyhedra Related to Combinatorial Problems I: A Minimizing Vertex of the Corner Polyhedron Gives an Optimal Integer Solution When the Right-Hand Side Lies Deep in the Basis ConeResearch Paper

An integer program in standard form, max⁡c⋅x\max c\cdot xmaxc⋅x subject to Ax=bAx=bAx=b, x≥0x\ge 0x≥0, xxx integer, is easy to state and hard to solve. Its linear programming relaxation is solved by the simplex method, which ends at an optimal basis BBB. The difference between the two problems is the integrality of xxx, and R. E. Gomory's 1969 paper Some polyhedra related to combinatorial…

11 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryDynamic ProgrammingOperations Research+1·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems VIII: Single-Controller Stochastic Games — a Dual Pair of Linear Programs Gives the Value and Stationary Optimal PoliciesTextbook

A two-person zero-sum stochastic game (also called a Markov game) is a Markov decision problem with two decision makers who pull in opposite directions: at every time point both players choose an action simultaneously, one player pays the other, and the system moves to a random next state whose law depends on the current state and both actions. Stochastic…

7 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems II: An Extreme Optimal Solution of the Dual Linear Program Yields a Pure Stationary Policy Optimal among Transient PoliciesTextbook

A Markov decision model describes a system that repeatedly occupies a state, receives a reward when an action is chosen, and then moves according to action-dependent probabilities. Termination may occur after any action. In a model with signed rewards, a policy that continues indefinitely can have a different total-reward behavior from one that eventually…

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

Outline of an Algorithm for Integer Solutions to Linear Programs: The Fractional Cut (3) Cuts Off the Simplex Solution but Keeps Every Nonnegative Integer Solution and the Integer Maximum of wResearch Paper

Integer linear programming asks for the best point whose coordinates are integers, even though linear programming methods naturally search over real points. In his 1958 note, Gomory describes a systematic way to add a constraint that excludes a fractional simplex solution while retaining every nonnegative integer solution. This mission isolates that single…

7 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems I: Five Equivalent Characterizations of a Transient Markov Decision Problem, among Them Contraction and a Finite Linear ProgramTextbook

Finite Markov decision models are often described by policies that choose an action from the current state. The admissible class in a total reward problem is wider: a randomized decision may use the complete history of observed states and chosen actions. For an undiscounted infinite horizon, the expected number of visits to a state may be infinite, and the…

12 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems III: Contracting Dynamic Programming — Pure, Stationary, Markov and General Policies Span One State-Action Frequency PolytopeTextbook

Finite Markov decision models describe repeated choices whose consequences depend on the present state. They are used when a planner needs one rule that works from every starting state, yet the rule may in principle respond to the entire observed history. Linear programming offers a different description: it records how often each state and action are used,…

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

On Approximate Solutions of Systems of Linear Inequalities: If Ax ≦ b Is Consistent, Every x Has a Solution x₀ with Fₙ(x − x₀) ≦ c·Fₘ((Ax − b)⁺)Research Paper

Iterative methods for a system of linear inequalities Ax≤bAx\le bAx≤b stop at a vector xˉ\bar xxˉ that only almost satisfies the system: the violation (Axˉ−b)+(A\bar x-b)^+(Axˉ−b)+ is small but not zero. A user then needs to know that xˉ\bar xxˉ is close to an actual solution. Hoffman's 1952 paper (J. Res. Nat. Bur. Standards 49) gives the first quantitative form of this fact: the…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

A Linear Programming Approach to the Cutting Stock Problem—Part II 1: The Lexicographic Knapsack Method Terminates, and M_1 Equals max(c_1, the Knapsack Optimum for the Longest Stock Length L_1)Research Paper

The cutting stock problem asks how to cut standard stock rolls of length LLL into pieces of demanded lengths l1,…,lml_1,\dots,l_ml1​,…,lm​ so that the demands are met at least cost. Gilmore and Gomory solved its linear programming relaxation by column generation (Part I, Opns. Res. 9 (1961)): every cutting pattern is a column, and the column to bring into the basis is found…

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

On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems 5: For Hypercube Uncertainty, Even in the Constraints, the Robust and Adaptive Optima CoincideResearch Paper

In two-stage optimization under uncertainty, a first-stage decision xxx is taken before the data are known, and a second-stage decision yyy is taken after a scenario ω\omegaω is revealed. The fully adaptive formulation lets yyy depend on ω\omegaω and minimizes the worst-case cost. It is the natural model of recourse, but it optimizes over policies, one decision per…

11 thms2 active usersReviewed
🏆Completed
Operations ResearchStatistics·Captain: mikedeng1

Optimal Estimation of Executive Compensation by Linear Programming I: Least Absolute Deviations under Ranking Constraints Equal a Linear ProgramResearch Paper

A firm may know salary bounds and the ranking of positions without having a reliable sample of individual salaries suitable for least-squares estimation. Charnes, Cooper and Ferguson used that kind of partial information to estimate a salary formula from ratings assigned to job factors. Their 1955 paper gives a model in which weights respect the job…

5 thms2 active usersReviewed
🏆Completed
Convex OptimizationDiscrete Geometry·Captain: mikedeng1

Integer Programming with a Fixed Number of Variables 2: A Simplex Satisfying (16) Rounds K, B(p,r) ⊂ τK ⊂ B(p,R) with R/r ≤ 2n^(3/2)Research Paper

In 1983 H. W. Lenstra, Jr. proved that integer linear programming with a fixed number of variables is solvable in polynomial time (Lenstra 1983). The algorithm became one of the founding results of algorithmic geometry of numbers: it introduced the strategy of making a convex body "round" by a linear change of coordinates, and then either finding a lattice…

7 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization·Captain: mikedeng1

Finding Minimum-Cost Circulations by Successive Approximation I: The Generic Refine Subroutine Stops Within 3n(n − 1) + 3nm + 3n²(m + n) Update Operations at an ε-Optimal CirculationResearch Paper

Minimum-cost circulation asks how to route flow around a directed network without accumulating flow at any vertex, while minimizing the total cost of the routed units. It is a basic network optimization problem: lower-bound and demand constraints in many flow models can be converted into circulation form. Goldberg and Tarjan's 1987 technical report develops…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Solving Large-Scale Zero-One Linear Programming Problems: A Minimal Cover Inequality Cuts Off x̄ iff the Knapsack Problem (2.12) Has Optimal Value Less Than OneResearch Paper

Large zero–one linear programs can contain constraints involving only a small fraction of their variables. Crowder, Johnson and Padberg study how to extract useful inequalities from one such row while solving the larger program. Their computational method identifies a violated inequality at a current linear programming solution, adds it, and resolves the…

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

On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems 4: For Symmetric Cost and Right-Hand-Side Uncertainty, the Adaptability Gap Is at Most FourResearch Paper

Two-stage optimization separates a decision made before uncertainty is observed from one made after a scenario is known. A fully adaptive policy can choose a different second-stage decision in each scenario, while a static robust solution commits to a single second-stage decision that works in every scenario. Static solutions can be simpler to implement,…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines That Run at Different Speeds: A min{K + 2√K + 1, 1.89 log m + O(√log m)}-Approximation for Q|prec|CmaxResearch Paper

Graham (1966) showed that list scheduling finds a schedule within a factor 222 of optimal for precedence-constrained jobs on identical parallel machines, the first performance guarantee for an approximation algorithm. When the machines run at different speeds (uniformly related machines), the same analysis breaks down, and for two decades the problem …

16 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Online Primal-Dual Algorithms for Covering and Packing 4: Online Rounding of the Fractional Routing Scheme Respects Capacities and Is O(log P(max)·[exp(1 + 2 ln m/u(min)) − 1])-CompetitiveResearch Paper

In online routing of virtual circuits, connection requests between pairs of nodes of a capacitated network arrive one at a time. Each request must be accepted and routed on a single path with bandwidth 111, or rejected, immediately and irrevocably, and no edge may carry more than its capacity. The goal is to maximize the number of accepted requests (the…

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

Assortment Optimization under Variants of the Nested Logit Model 1: If the Restricted LP Optimum Scaled by α Is Feasible for the Full LP, Its Assortment Earns Within a Factor α of the Optimal RevenueResearch Paper

A retailer that sells products in several categories, channels or stores has to decide which products to offer in each. Customers substitute: a product left out of the assortment sends some of its demand to other products, and some of it away. The nested logit model (McFadden 1974, 1981) is the standard choice model for this situation. It groups products…

6 thms2 active usersReviewed
PreviousPage 16 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