A coordinated effort to formalize the mathematics of operations research in Lean 4.
Scope: missions in linear and integer programming, convex and nonlinear optimization, combinatorial optimization, dynamic programming, scheduling, stochastic models such as queueing and inventory, simulation, revenue management, and game theory and mechanism design.
On the Power and Limitations of Affine Policies in Two-Stage Adaptive Optimization V: The Optimal First Stage over a Dominating Simplex Is a 4√m-ApproximationResearch Paper
Two-stage adaptive optimization models decisions taken in two steps: a first-stage decision x is fixed before an uncertain right-hand side b is revealed, and a second-stage decision y(b) is chosen afterwards, with the worst case over an uncertainty setU to be minimized. Problems of this form arise in capacity planning, network design and inventory…
Constructing Uncertainty Sets for Robust Linear Optimization 3: The Largest Centrally Symmetric Distortion Inner Approximation of a Polytope Solves a Linear ProgramResearch Paper
A robust linear constrainta′x≥b for all a∈U protects a decision x against every realization of the data a in an uncertainty setU. Robust optimization took this form in the work of Ben-Tal and Nemirovski (Math. Oper. Res. 1998; Oper. Res. Lett. 1999), where U is chosen by the modeller. Bertsimas and Brown (Oper. Res. 2009)…
Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons 3: With a Discrete Price Set the Two-Price Stopping-Time Heuristic Is Asymptotically OptimalResearch Paper
Airlines, hotels and cruise lines rarely change prices continuously. They sell a fixed product (seats on one flight, rooms on one night) over a finite selling season, and they sell it at a small set of fares, opening and closing fare classes as the season unfolds. Gallego and van Ryzin, in Optimal Dynamic Pricing of Inventories with Stochastic Demand over…
On the Abstract Properties of Linear Dependence 4: Orthogonal Subspaces Have Dual MatroidsResearch Paper
Hassler Whitney introduced matroids in On the Abstract Properties of Linear Dependence (Amer. J. Math. 57, 1935, doi:10.2307/2371182) to capture what linear dependence among the columns of a matrix and the circuit structure of a graph have in common. One of the central constructions of the paper is duality. For graphs, duality exists only for planar graphs…
Robust Solutions of Uncertain Linear Programs II: With Ellipsoidal Uncertainty the Robust Counterpart Is Equivalent to a Conic Quadratic ProgramResearch Paper
The data of a linear program are often not known exactly: they are measured or estimated, or they are forecasts. The robust counterpart approach, going back to Soyster (1973), asks for a solution that is feasible for every data matrix in a prescribed uncertainty set and is best among such solutions. Ben-Tal and Nemirovski's 1999 paper [1] showed that the…
Constructing Uncertainty Sets for Robust Linear Optimization 1: A Distortion Risk Constraint Equals a Robust Constraint over a Permutohull and an Explicit Linear SystemResearch Paper
Robust linear optimization replaces an uncertain constraint a~′x≥b by the requirement that a′x≥b hold for every a in an uncertainty setU (Ben-Tal and Nemirovski 1999). The method leaves open where U should come from. Risk theory answers a related question from the other side: a decision maker's attitude to an uncertain…
Constructing Uncertainty Sets for Robust Linear Optimization 2: The Distortion Risk Measures with Centrally Symmetric Permutohulls Are the Mixtures of ⌊N/2⌋+1 GeneratorsResearch Paper
A linear decision made with uncertain coefficients can be protected by requiring the constraint to hold for every coefficient vector in an uncertainty set. Choosing that set determines how conservative the decision is. Bertsimas and Brown connect this choice to a risk measure: a functional that assigns a cost to the random reward left by a decision. Their…
Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons 1: A Fixed Price Earns at Least 1 − 1/(2√min{n, λ*t}) of the Optimal Expected RevenueResearch Paper
A firm holds a fixed stock of a perishable or seasonal product: airline seats, hotel rooms, fashion goods, tickets. It must sell the stock over a finite season, and whatever is left at the end is worth nothing. The firm can change its price at any time, and demand responds to the price at random. Should it adjust its price continually as sales occur and…
Scheduling a Multi Class Queue with Many Exponential Servers: Asymptotic Optimality in Heavy Traffic: The HJB-Based Preemptive Policy Is Asymptotically Optimal Among Work-Conserving PoliciesResearch Paper
Large call centers route several types of customers to a common pool of agents. When the pool is large and highly utilized, the relevant asymptotic regime is the quality-and-efficiency-driven (QED) or Halfin–Whitt regime (Halfin & Whitt 1981). The number of servers n grows while the offered load stays within O(n) of n. Waiting is then neither…
Computational Issues in an Infinite-Horizon, Multiechelon Inventory Model 3: A Closed Form for the Induced Penalty Cost under Normal DemandResearch Paper
Multiechelon inventory theory studies supply systems in which stock is held at several levels: here, a depot that orders from an outside supplier and a retail outlet that is replenished from the depot and faces random customer demand. The question is how much to order and ship in each period so as to minimize expected holding, shortage and ordering costs…
Optimal Control of Markov Processes with Incomplete State Information 1: Reduction to Complete State Information on the Conditional State Distributions, with the Same Optimal LawResearch Paper
A controller often cannot see the state of the system it steers. It sees only measurements that are noisy functions of that state. In operations research this happens in machine maintenance and inspection, in queues observed only partially, and in inventory systems with inexact stock records. In control engineering it is the usual case. The question is what…
Contraction Mappings in the Theory Underlying Dynamic Programming 1: Under the Contraction and Monotonicity Assumptions the Solution of the Functional Equation Is the Optimal ReturnResearch Paper
Dynamic programming often replaces a search over whole plans with an equation for a value function. That replacement is useful only when solving the equation recovers the value actually available through policies. In his 1967 paper, Eric Denardo isolated conditions on an abstract return function that make this identification possible, without committing to…
On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift 1: Projected Gradient Ascent on the Simplex Is ε-Optimal After 64γ|S||A|D∞²/((1−γ)⁶ε²) IterationsResearch Paper
Policy gradient methods optimize a parameterized policy of a Markov decision process by gradient ascent on its expected discounted return. They are among the most widely used methods in reinforcement learning, from REINFORCE (Williams 1992) and the policy gradient theorem to natural policy gradient and trust-region methods. The objective is not concave in…
Simultaneously Learning and Optimizing Using Controlled Variance Pricing 2: Certainty Equivalent Pricing Fails to Converge to the Optimal Price with Positive ProbabilityResearch Paper
A seller who does not know how demand responds to price has to learn the demand curve from its own sales while it is selling. The most natural policy is certainty equivalent pricing (also called myopic pricing or passive learning): after every period, estimate the unknown demand parameters from all data collected so far, and charge the price that would be…
Robust Wasserstein Profile Inference and Applications to Machine Learning 1: Square-Root LASSO Is Wasserstein DRO — the Worst-Case Squared Loss over D_c(P, P_n) ≤ δ Equals (√MSE_n(β) + √δ‖β‖_p)²Research Paper
Regularized least squares is the standard tool of high-dimensional linear regression. The square-root LASSO of Belloni, Chernozhukov and Wang (Biometrika, 2011) minimizes MSEn(β)+λ∥β∥1. Unlike the LASSO, its optimal regularization parameter does not depend on the unknown noise level. Regularization is usually justified…
Oracle-Based Robust Optimization via Online Learning 1: The Dual-Subgradient Meta-Algorithm Returns a 2ε-Approximate Robust Solution or Certifies Infeasibility within ⌈G²D²/ε²⌉ Oracle CallsResearch Paper
Robust optimization protects a decision against every realization of uncertain data in a prescribed uncertainty set. The standard approach replaces the uncertain constraints by a deterministic robust counterpart and solves that counterpart directly (Ben-Tal, El Ghaoui, Nemirovski, Robust Optimization, 2009). The counterpart is often a harder problem than…
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results 4: A Fixed Boolean Combination of k Classes Has Gaussian Complexity at Most 2 Σ_j G_n(F_j)Research Paper
Data-dependent risk bounds in statistical learning replace combinatorial quantities such as the VC dimension with averages of how well a function class can fit random noise on the observed sample. Bartlett and Mendelson's article (JMLR 3, 2002) established these averages, the Rademacher and Gaussian complexities, as a general tool: a risk bound (their…
Optimization with Stochastic Dominance Constraints: Lagrange Multipliers of a Second-Order Dominance Constraint Are Concave Nondecreasing Utility FunctionsResearch Paper
A decision maker choosing a random outcome X (a portfolio return, a policy's cost savings, a schedule's throughput) often has a reference outcomeY, the result of a benchmark policy, and wants the new outcome to be preferable to it for every risk-averse decision maker, not just on average. Expected-utility theory (von Neumann and Morgenstern) makes this…
Uniformly Bounded Regret in the Multi-Secretary Problem 2: When (f₁+ε)n ≤ k ≤ (1−fₘ−ε)n, Every Non-Adaptive Policy Has Regret at Least M√nResearch Paper
The multi-secretary problem is the basic model of selecting under a budget from a stream of offers. Hiring a fixed number of candidates, accepting a fixed number of requests for a perishable resource, and admitting customers into a capacity-limited service all have this structure. Each item must be accepted or rejected on arrival, and the comparison point…
Uniformly Bounded Regret in the Multi-Secretary Problem 1: The Budget-Ratio Policy Has Regret at Most a₁M(ε), Uniformly in the Number of Candidates n and the Budget kResearch Paper
The multi-secretary problem is the simplest model of capacity allocation under uncertainty: a decision maker sees n candidates one at a time and may hire at most k of them, with every decision final. The same structure underlies single-resource revenue management (accepting or rejecting booking requests against a fixed inventory; see Talluri and van Ryzin, T…
Assortment Optimization under Variants of the Nested Logit Model 4: With Dissimilarity Parameters at Most One, the Knapsack-Relaxation and Singleton LP Optimum Scaled by 2 Is Feasible for the Full LPResearch Paper
Assortment optimization asks which set of products a firm should offer when customers choose among the offered products according to a discrete choice model; it underlies shelf-space planning in retail and fare-class control in airline revenue management (Talluri and van Ryzin, 2004). Under the nested logit model products are grouped into nests, and a…
Assortment Optimization under Variants of the Nested Logit Model 2: With Dissimilarity Parameters at Most One and Fully-Captured Nests, a Nested-by-Revenue Assortment in Every Nest Is OptimalResearch Paper
A retailer choosing which products to display, or an airline choosing which fare classes to open, solves an assortment optimization problem: pick the set of offered products that maximizes expected revenue when customers choose among what is offered according to a discrete choice model. Under the multinomial logit model the answer has a simple form: an…
Stochastic Optimal Control: The Discrete-Time Case IX: Imperfect State Information — Reduction to a Perfect-Information Model through a Statistic Sufficient for ControlTextbook
In most control problems the controller does not see the state of the system. It sees noisy observations, remembers its past controls, and must act on that record. Inventory systems with delayed or inaccurate counts, maintenance of machines whose wear is only inspected, target tracking, and medical treatment planned from test results all have this form. The…
On the Power and Limitations of Affine Policies in Two-Stage Adaptive Optimization IV: When A ≥ 0 the Best Affine Policy Costs at Most 3√m Times the Fully Adaptable OptimumResearch Paper
Two-stage adaptive optimization models decisions taken in two steps: a first-stage decisionx is fixed before an uncertain right-hand side b is revealed, and a second-stage decisiony(b) is chosen after it, as a function of b. The objective protects against the worst b in an uncertainty setU. Computing an optimal fully adaptable solution is…
Explicit Expanders of Every Degree and Size 1: For Distinct Primes q₁, q₂, Every Large n Has an LPS Vertex Count Q(q₁, q₂, s, t) Between n and n + o(n)Research Paper
An (n,d,λ)-graph is a d-regular graph on n vertices in which every eigenvalue of the adjacency matrix other than the top eigenvalue d has absolute value at most λ. Graphs of this kind with λ small compared with d are expanders. They are used in derandomization, error-correcting codes, sorting networks and many other constructions in…