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
Mechanism DesignOperations Research·Captain: mikedeng1

Optimal Design for Multi-Item Auctions: A Robust Optimization Approach: The Robust Optimal Mechanism Is Incentive Compatible, Budget Feasible and Individually RationalResearch Paper

Designing a revenue-maximizing auction for several items is hard once buyers have budgets. Myerson's optimal auction (Myerson 1981) solves the single-item problem without budgets, under a known prior on the buyers' values. With several items, correlated values or budget constraints, no comparable characterization is known, and the Bayesian formulation…

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

Stochastic Dual Dynamic Integer Programming 2: Lagrangian Cuts from the Local-Copy Reformulation Are Valid and Tight at Binary StatesResearch Paper

Multistage stochastic integer programs model sequential decisions under uncertainty in which some decisions are discrete: unit commitment in power systems, capacity expansion, production planning with setups. Their linear (continuous) counterparts are routinely solved by nested decomposition methods such as stochastic dual dynamic programming (SDDP; Pereira…

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

Production Scheduling for Strategic Open Pit Mine Planning: A Mixed-Integer Programming Approach 3: Variable-Right-Hand-Side Production Cuts along a Precedence Chain Are ValidResearch Paper

Strategic open pit mine planning decides which parts of an ore body are excavated, in which period, and where each block of material is sent: to a processing plant, a stockpile or a waste dump. Rivera Letelier, Espinoza, Goycoolea, Moreno and Muñoz (Operations Research 68(5), 2020) state the problem as a mixed-integer program, the precedence-constrained…

7 thms2 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness III: Adaptive Restarts Take at Most ⌈2C(q+2)/(αβ)⌉ Inner Steps and Converge Linearly on Sharp ProblemsResearch Paper

First order primal–dual algorithms are used when a linear program is too large for a direct factorization or when matrix operations are cheaper than solving a sequence of linear systems. Their basic guarantees often bound an averaged duality gap by a quantity proportional to 1/t1/t1/t after ttt steps. A restart discards the current inner iteration history and…

8 thms2 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness II: Fixed-Frequency Restarts Shrink the Distance to the Solution Set by β per Restart on Sharp ProblemsResearch Paper

Linear programs at very large scale are increasingly solved by first-order primal-dual methods, which use only matrix-vector products instead of matrix factorizations. Such methods parallelize well and have a small memory footprint, but on their own they are slow to reach moderate or high accuracy. Applegate, Hinder, Lu and Lubin (arXiv:2105.12715, Math.…

8 thms2 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness I: The LP Saddle-Point Problem Is 1/(H(K)√(1+4R²))-Sharp on Every Ball W_R(0)Research Paper

First-order primal-dual methods (PDHG, extragradient, ADMM) are the engine of a new generation of large-scale linear programming solvers, such as PDLP, because they need only matrix–vector products with the constraint matrix. Their textbook guarantees for convex–concave saddle-point problems are sublinear, O(1/t)O(1/t)O(1/t) for the averaged iterate, while in practice…

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

Online Primal-Dual Algorithms for Covering and Packing 2: The Phased Online Fractional Covering Scheme Covers Every Constraint to 1/B at Cost at Most 8 log(2n)/B Times the OptimumResearch Paper

Online covering models decisions that must be made as requirements arrive. A planner knows the cost of each available resource, but learns the requirements one at a time and cannot undo an allocation already made. This occurs, for example, when requests for network service or elements needing coverage appear over time. The central question is how much more…

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

Obtaining Lower Bounds from the Progressive Hedging Algorithm for Stochastic Mixed-Integer Programs: The Dual Prices Give a Lower Bound on the Optimal Value in Every IterationResearch Paper

Progressive hedging separates a stochastic optimization problem by scenario, solves those smaller problems, and coordinates their first-stage decisions through weighted aggregation and price updates. It is useful when the full extensive formulation is too large to solve directly. For stochastic mixed-integer programs, its iterates can provide feasible…

4 thms2 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: mikedeng1

Strong Mixed-Integer Programming Formulations for Trained Neural Networks 2: Under Strict Activity Every Inequality of the Exponential Family (6b) Is Facet-DefiningResearch Paper

Trained neural networks are increasingly embedded inside optimization models: to verify that a classifier is robust to small input perturbations, to optimize over a learned surrogate of an expensive system, or to choose decisions whose outcome is predicted by a network. When the network uses rectified linear units (ReLU), each neuron y=max⁡{0, w⋅x+b}y=\max\{0,\,w\cdot x+b\}y=max{0,w⋅x+b}…

5 thms2 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: mikedeng1

Strong Mixed-Integer Programming Formulations for Trained Neural Networks 1: A ReLU Neuron over a Box Has an Ideal Formulation with One Binary Variable and the Exponential Family (6b)Research Paper

A trained feed-forward neural network with ReLU activations, ReLU(v)=max⁡{0,v}\mathrm{ReLU}(v)=\max\{0,v\}ReLU(v)=max{0,v}, is a piecewise linear function of its input. Many tasks ask for an optimization over such a network with its weights held fixed: verifying that no small perturbation of an image changes its classification, finding adversarial examples, or embedding a learned model of…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOptimal Transport·Captain: mikedeng1

Computational Optimal Transport IV: The Support Graph of an Extreme Point of the Transportation Polytope U(a, b) Has No Cycle, Hence at Most n + m − 1 Nonzero EntriesTextbook

Discrete optimal transport between two histograms is a linear program. Its feasible set, the transportation polytope, has been studied since Hitchcock (1941) and Kantorovich, and the structure of its vertices underlies the classical algorithms for the problem: the north-west corner rule produces a vertex, and the network simplex moves from vertex to vertex.…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsOptimal TransportOptimization·Captain: mikedeng1

Computational Optimal Transport I: For Uniform Marginals 1/n Some Permutation Matrix Solves the Kantorovich Problem, so the Relaxation of Optimal Assignment Is TightTextbook

An assignment problem pairs each of nnn sources with exactly one of nnn destinations while minimizing a specified cost. A permutation records those pairings. The number of permutations grows as n!n!n!, so a direct search quickly becomes impractical. In discrete optimal transport, the same data can be placed in a linear optimization problem over nonnegative…

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

Constrained Assortment Optimization for the Nested Logit Model 6: Under Space Constraints, the Linear Program (13) over Knapsack-Relaxation Solutions Bounds the Optimal Expected RevenueResearch Paper

A retailer that sells products in several categories has to decide which products to put on display. Under the nested logit model a customer first picks a category (a nest) and then a product inside it, so offering a product changes the purchase probabilities of every other product. Choosing the assortment that maximizes expected revenue is assortment…

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

Constrained Assortment Optimization for the Nested Logit Model 1: The Assortment Stitched from the Linear Program (4) Is the Best Among All Combinations of the Candidate AssortmentsResearch Paper

An assortment planner chooses which products to offer to arriving customers. When products are grouped into nests, a customer's choice of nest depends on all the assortments offered at once. A planner may nevertheless be able to generate only a short list of promising assortments for each nest. The remaining task is to choose one assortment from each list…

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

Primal and Dual Linear Decision Rules in Stochastic and Robust Optimization 3: In Multistage Programs, the Primal and Dual Linear Decision Rule Problems Equal the LPs (4.2) and (4.6)Research Paper

A linear multistage stochastic program chooses decisions over TTT stages while a random vector is revealed one piece at a time; each decision may depend only on what has been observed so far. Such programs model production planning, capacity expansion, hydro scheduling and portfolio problems. Computing their optimal value exactly is intractable in general:…

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

A Branch-and-Cut Algorithm for the Dial-a-Ride Problem: The Generalized Order-Matching Inequality x(H) + Σ x(T_h) ≤ |H| + Σ|T_h| − 2m Is Valid for Every Feasible Route PlanResearch Paper

The dial-a-ride problem (DARP) asks for minimum-cost vehicle routes that carry users from individual pick-up points to individual drop-off points, subject to vehicle capacities, time windows, route durations and a bound on each user's ride time. It models door-to-door transport for elderly and disabled people, shared taxis and on-demand microtransit.…

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

Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal 2: Under Lower and Upper Degree Bounds, Iterative Rounding Finds a Connecting Tree of LP Cost within A_v − 1 and B_v + 1Research Paper

Network design problems often ask for a cheap spanning tree in which no vertex is overloaded: in multicast and overlay networks the degree of a node bounds the number of copies it must forward, and in physical networks it bounds the number of ports. The minimum bounded degree spanning tree problem asks for a minimum-cost spanning tree whose degrees respect…

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

Worst-Case Conditional Value-at-Risk with Application to Robust Portfolio Management 3: Under Box Uncertainty, Worst-Case CVaR Minimization (16)–(20) Is Equivalent to the Linear Program (24)–(30)Research Paper

Conditional value-at-risk (CVaR) is the expected loss in the worst (1−β)(1-\beta)(1−β) fraction of outcomes. Rockafellar and Uryasev showed that, for a finite set of scenarios, minimizing CVaR is a linear program whenever the loss is linear in the decision (Rockafellar–Uryasev 2000; 2002). That linear program needs the scenario probabilities, and in practice they are…

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

Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal 1: Iterative Rounding Finds a Spanning Tree of Cost at Most the LP Optimum with Every Degree at Most B_v + 1Research Paper

A network designer may need a cheap connection that keeps the number of links at each site within a local capacity. The minimum bounded-degree spanning tree problem asks for the cheapest spanning tree of a weighted, undirected graph whose vertex degrees respect prescribed upper bounds. The capacity constraints matter in settings where a low-cost tree alone…

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

Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case 2: The Greedy Forward Dual Solution Is Optimal and Its Value Is the Lot-Sizing CostResearch Paper

Economic lot sizing asks when to produce goods across a finite planning horizon when demand in each period is known. Producing in a period incurs a fixed setup charge and a marginal cost per unit, while goods may be produced before the period in which they are needed. Such a decision has to balance paying another setup charge against producing more units…

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

Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming: The Set-Inclusive LP Has the Same Feasible Set as the LP of Support FunctionalsResearch Paper

A linear program max⁡c⋅x\max c\cdot xmaxc⋅x subject to Ax≤bAx\le bAx≤b, x≥0x\ge 0x≥0 assumes that the constraint matrix AAA is known exactly. In practice the columns of AAA — the activity vectors, describing how much of each resource one unit of activity jjj consumes — are estimates. A. L. Soyster's 1973 technical note in Operations Research (doi:10.1287/opre.21.5.1154) asked what a…

12 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
PreviousPage 12 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