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
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

Cones of Matrices and Set-Functions and 0–1 Optimization III: The Defect of a Stable Set Inequality Bounds Its N-IndexResearch Paper

Many 0–1 optimization problems can be written as linear programs over the convex hull of the 0–1 points of a polytope, but that hull usually has no manageable description by inequalities. Lift-and-project methods approximate it by a sequence of convex sets. Each set comes from a linear or semidefinite system in more variables, followed by a projection.…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Cones of Matrices and Set-Functions and 0–1 Optimization I: n Rounds of the Lovász–Schrijver N Operator Give the 0–1 HullResearch Paper

A 0–1 integer program asks for the best 0–1 vector satisfying a system of linear inequalities. Its linear relaxation is easy to optimize over, but the relaxation is usually much larger than the convex hull of the 0–1 solutions. Lift-and-project methods close this gap systematically: they lift the relaxation to a higher-dimensional space, add constraints…

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

Validation of Subgradient Optimization II: A Unique Optimal Assignment Makes the Dual Optimal Set Full-DimensionalResearch Paper

The subgradient method maximizes a concave, piecewise-linear function w(π)=min⁡k{ck+π⋅vk}w(\pi)=\min_k\{c_k+\pi\cdot v_k\}w(π)=mink​{ck​+π⋅vk​} by moving along a subgradient vkv_kvk​ of an active piece with a prescribed step. Held, Wolfe and Crowder's 1974 paper Validation of subgradient optimization tested the method on three families of Lagrangean duals from combinatorial optimization — the…

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

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma: ℓ1-Proximity of Integer and LP OptimaResearch Paper

Integer programs are routinely solved by first solving their linear programming (LP) relaxation and then searching for an integer optimum near the fractional one. How near an integer optimum must be is the subject of proximity theorems. They bound the search region of branch-and-bound and of dynamic programming, and they turn a fractional optimum into a…

12 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimal Transport·Captain: mikedeng1

Scenario Reduction in Stochastic Programming: The Optimal Redistribution Rule and the Explicit Kantorovich Distance of a Reduced MeasureResearch Paper

Stochastic programs are solved in practice on a finite set of scenarios: a discrete probability distribution P=∑i=1NpiδωiP=\sum_{i=1}^N p_i\delta_{\omega_i}P=∑i=1N​pi​δωi​​ that approximates the true distribution of the uncertain data. The size of the resulting deterministic problem grows with NNN, and for multistage models it grows very fast, so NNN is often reduced before solving. The…

7 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchOptimization+1·Captain: naimengye

Multi-armed Bandit Allocation Indices IV: The Achievable Region, Generalized Conservation Laws and the Adaptive Greedy AlgorithmTextbook

Chapter 5 of Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/9780470980033), presents the achievable region methodology of Tsoucas, Bertsimas and Niño-Mora, Glazebrook and Garbe, and Dacre, Glazebrook and Niño-Mora: instead of arguing about policies, one argues about the set of performance vectors they can produce.…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Introduction to Stochastic Programming III: The L-Shaped Method and Its Finite ConvergenceTextbook

Two-stage stochastic programs with recourse — choose a first-stage decision xxx now, observe a random outcome ξ\xiξ, then choose a second-stage recourse decision y(ξ)y(\xi)y(ξ) to repair whatever xxx left infeasible or suboptimal — are the workhorse model of the field, used for capacity planning, inventory and financial portfolio problems since the 1950s (Dantzig 1955;…

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

Introduction to Linear Optimization XII: Interior Point Methods and Path FollowingTextbook

Interior point methods solve linear programs by moving through the interior of the feasible set instead of along its edges — the approach that turned Karmarkar's 1984 breakthrough into today's practical large-scale solvers. This mission formalizes the primal path following algorithm of Chapter 9 of Bertsimas–Tsitsiklis. For μ>0\mu > 0μ>0 the logarithmic barrier

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

Introduction to Linear Optimization XI: The Ellipsoid MethodTextbook

Can the feasibility of a system of linear inequalities be decided in a provably small number of iterations? The ellipsoid method — the algorithm with which Khachiyan showed in 1979 that linear programming is polynomially solvable — answers this with pure convex geometry. This mission formalizes Chapter 8 of Bertsimas–Tsitsiklis. An ellipsoid is

14 thms3 active usersReviewed
🏆Completed
Optimization·Captain: Shuze Chen

Introduction to Linear Optimization IX: Network Flow IntegralityTextbook

Why do network linear programs return integer answers for free? This mission formalizes the structural theory of the minimum cost network flow problem of Chapter 7 of Bertsimas & Tsitsiklis: a directed graph G=(N,A)G=(\mathcal{N},\mathcal{A})G=(N,A) with external supplies bib_ibi​, arc costs cijc_{ij}cij​, and the node-arc incidence matrix A\mathbf{A}A — an n×mn\times mn×m matrix in which…

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

Introduction to Linear Optimization VIII: Sensitivity Analysis and Subgradients of the Optimal CostTextbook

How does the optimal cost of a linear program respond when the problem data change? Chapter 5 of Bertsimas-Tsitsiklis studies the standard form problem min⁡{c′x∣Ax=b, x≥0}\min\{c'x \mid Ax = b,\ x \ge 0\}min{c′x∣Ax=b, x≥0} (rows of AAA linearly independent) as the requirement vector bbb and the cost vector ccc vary. On the convex set S={b∣P(b)≠∅}S = \{b \mid P(b) \neq \emptyset\}S={b∣P(b)=∅} of feasible right-hand sides,…

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

Introduction to Linear Optimization V: Duality TheoryTextbook

Every linear programming problem has a shadow. To the primal min⁡c′x\min c'xminc′x we associate the dual max⁡p′b\max p'bmaxp′b, whose variables price the primal constraints: one dual variable per primal constraint and one dual constraint per primal variable, with signs governed by the correspondence of Table 4.1. This mission formalizes §4.1–4.5 of Bertsimas–Tsitsiklis: the dual of…

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

Introduction to Linear Optimization IV: The Simplex MethodTextbook

How does one actually solve a linear program? Chapter 2 showed that if a standard-form problem min⁡c′x\min c'xminc′x subject to Ax=bAx = bAx=b, x≥0x \ge 0x≥0 has an optimal solution, it has an optimal basic feasible solution; the simplex method searches among basic feasible solutions, moving along edges of the feasible set in cost-reducing directions. This mission formalizes the…

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

Introduction to Linear Optimization I: Polyhedra and Basic Feasible SolutionsTextbook

Every linear programming problem asks to minimize a linear cost c′xc'xc′x over a polyhedron — a set of the form P={x∈Rn∣Ax≥b}P = \{x \in \mathbb{R}^n \mid Ax \ge b\}P={x∈Rn∣Ax≥b}, or in standard form {x∣Ax=b, x≥0}\{x \mid Ax = b,\ x \ge 0\}{x∣Ax=b, x≥0}. Chapter 2 of Bertsimas–Tsitsiklis develops the geometry of these feasible sets, and its central achievement is making the intuitive notion of a "corner point"…

9 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: iris

Combinatorial Optimization (Cook et al.) II: When Least-Cost Dipaths Exist, the Shortest Dipath Cost Equals the Maximum Feasible PotentialTextbook

The shortest path problem asks, in a network whose links carry costs, for a cheapest directed route from a fixed origin to every other point. It is the basic subroutine of network optimization: minimum-cost flow algorithms, matching algorithms and many dynamic programs call it repeatedly, and arc costs that are negative arise naturally, for instance as −log⁡-\log−log…

22 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: iris

Combinatorial Optimization (Cook et al.) V: A Minimum-Cost Flow Problem with Integral Demands and Capacities Has an Integral Optimal SolutionTextbook

The minimum-cost flow problem is the common roof over shortest paths, maximum flows, transportation and assignment problems, and transshipment. It asks for the cheapest way to move a commodity through a directed network so that every node receives its prescribed net amount and no arc carries more than its capacity. Its central structural fact is…

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

Sparse Solutions of a Class of Constrained Optimization Problems: For All Small p > 0, Every Lp Minimizer under an L1 Constraint Is a Sparsest Solution, and the Solution Set StabilizesResearch Paper

Many problems in signal processing, statistics and compressed sensing ask for a sparse solution of an underdetermined, possibly noisy linear system: a vector x∈Rnx\in\mathbb R^nx∈Rn with as few nonzero entries as possible such that AxAxAx is close to bbb. The direct formulation, minimizing the number of nonzeros ∥x∥0\|x\|_0∥x∥0​, is combinatorial and NP-hard in general. A…

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

Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems: The Maximum Support Algorithm Is Correct and Terminates Within Condition-Measure BoundsResearch Paper

Finding a nonzero nonnegative point in a linear subspace is the feasibility core of linear optimization. For a subspace L⊆RnL \subseteq \mathbb R^nL⊆Rn with orthogonal complement L⊥L^\perpL⊥, the pair of problems

7 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: mikedeng1

New Combinatorial Insights for Monotone Apportionment: House-Monotone and Quota-Compliant Apportionments Are the Seat Counts of Extreme Points of a Network Flow LP with Lookahead Φ(p, H)Research Paper

An apportionment method distributes the HHH seats of a house among nnn states in proportion to their populations. Exact proportionality is impossible with integer seats, so methods are judged by axioms. Two axioms date back to the debates over the seats of the US House of Representatives. Quota compliance asks that each state receive its exact proportional…

8 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationStochastic Systems·Captain: mikedeng1

Blind Dynamic Resource Allocation in Closed Networks via Mirror Backpressure: Mirror Backpressure Loses at Most O(K/T + 1/K + √(ηK)) Payoff per CustomerResearch Paper

Ride-hailing, car-sharing and bike-sharing platforms, as well as scrip systems, move a fixed stock of reusable resources around a network. Each customer that is served relocates one unit, from a pick-up location to a drop-off location. The operator decides, customer by customer, whether to serve and with which unit. Supply can run dry at a location, which…

15 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Near-Optimal Bayesian Online Assortment of Reusable Resources: the hybrid simulation-based algorithm is (1 − min{1/2, ε*(c_min)})-competitive against the Bayesian expected LPResearch Paper

Rental platforms, cloud computing, hotel and car-rental systems, and on-demand services all sell access to reusable resources: a unit that is rented comes back after a random rental duration and can be rented again. When such a platform displays a menu of products (an assortment) to each arriving customer, it faces an online decision problem: offering a…

15 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOperations Research·Captain: mikedeng1

Fully Polynomial-Time Approximation Schemes for Fair Rent Division: Algorithm 1 on the Slope-Rounded Instance Halts in Polynomially Many Iterations with an ε-Envy-Free SolutionResearch Paper

Housemates who share a house must decide who gets which room and how the total rent is split. A solution pairs an assignment of rooms to agents with a rent for each room, and it is envy-free if no agent prefers another room at that room's rent. Envy-free rent division is the textbook example of fair division with money and is the mathematical core of…

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

Feasible Bases for a Polytope Related to the Hamilton Cycle Problem: Every Ultimate Feasible Basis Is a Good Augmented Spanning Tree Whose Thick Arcs Form the Unique Perfect MatchingResearch Paper

A Hamilton cycle visits every vertex of a directed graph once and returns to its start. Finding one is a standard combinatorial optimization problem, and linear programming provides a way to study it through extreme points. Kalinowski and Mohammadian examine a polytope introduced for this purpose and ask what its feasible bases look like when a discount…

9 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: Shuze Chen

Interior Point Algorithms VI: Predictor Directions Are O(μ) on the Optimal PartitionTextbook

Primal-dual interior-point methods for linear programming come with two kinds of guarantee. The worst-case one is a bound of O(nlog⁡(R/ϵ))O(\sqrt n\log(R/\epsilon))O(n​log(R/ϵ)) iterations to reduce the duality gap below ϵ\epsilonϵ. The asymptotic one says what happens to the duality gap near the end of the run, where practical codes spend their final iterations. For the…

11 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: Shuze Chen

Interior Point Algorithms V: Random Gaussian Feasibility Problems Are Strictly Feasible on One SideTextbook

Worst-case analysis of interior-point methods gives iteration bounds of order n L\sqrt n\,Ln​L or nlog⁡(1/ϵ)\sqrt n\log(1/\epsilon)n​log(1/ϵ), while practical codes finish in a number of iterations that barely grows with the problem size. Chapter 6 of Yinyu Ye's Interior Point Algorithms: Theory and Analysis (Wiley 1997, doi:10.1002/9781118032701) addresses the gap…

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