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.
Online Stochastic Matching: Beating 1-1/e 2: The Suggested Matching Algorithm Achieves 1 − 1/e with High Probability, and This Is Tight Even in ExpectationResearch Paper
Online bipartite matching models decisions that must be made as requests arrive: an advertiser can be assigned to a compatible request once, and an assignment cannot be revised when later requests reveal a better alternative. Display advertising is the motivating example in Feldman, Mehta, Mirrokni, and Muthukrishnan's 2009 preprint: an ad server knows…
On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift 6: Agnostic Q-NPG for Log-Linear Policies, Bounded by Transfer Error, Excess Risk and Condition NumberResearch Paper
Policy gradient methods optimize a decision rule by changing the parameters that determine its action probabilities. In reinforcement learning, the objective is the expected total reward collected over time. Once a policy is restricted to a feature-based class, the best policy may be less effective than the unrestricted optimum. A useful guarantee must…
On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift 2: On a Chain MDP All Low-Order Derivatives of the Value Are Exponentially Small at Suboptimal PoliciesResearch Paper
Policy gradient methods adjust a policy by following derivatives of its expected reward. A common expectation is that a small gradient indicates a policy close to optimal. For discounted Markov decision processes, that interpretation can fail when a policy rarely reaches the states where reward is available. Agarwal, Kakade, Lee, and Mahajan study this…
Optimality and Duality Theory for Stochastic Optimization Problems with Nonlinear Dominance Constraints 3: The Dual Functional of a Dominance Constraint Is Minus an Expected Concave ConjugateResearch Paper
A stochastic dominance constraint asks a random outcome X of a decision to be at least as good as a benchmark outcome Y for every risk-averse decision maker: in the second-order version, E[u(X)]≥E[u(Y)] for every concave nondecreasing utility u. Dentcheva and Ruszczyński introduced optimization problems with such constraints in Optimizati…
Stability and Instability of Fluid Models for Reentrant Lines 3: In Every Reentrant Line the Last-Buffer-First-Served Fluid Model Is StableResearch Paper
A manufacturing line can send the same job through several stations and return it to a station it visited earlier. Semiconductor fabrication is one example. Such a reentrant line has several customer classes at one server, and the server must choose which class to work on. A station may have enough capacity on average yet the line can still accumulate an…
Stability and Instability of Fluid Models for Reentrant Lines 2: In Every Reentrant Line the First-Buffer-First-Served Fluid Model Is StableResearch Paper
Semiconductor wafer fabrication is the standard example of a reentrant line: every wafer follows the same long route through a set of machines, and visits several machines many times. Each visit is a separate processing step, and a machine with work waiting from several steps must choose which step to serve. Kumar (1993) proposed studying such lines through…
Online Primal-Dual Algorithms for Covering and Packing 3: A Deterministic O(log d log(n/OPT))-Competitive Algorithm for Online Unweighted Set CoverResearch Paper
Online set cover is the basic covering problem in which the requests arrive over time. A ground set of elements and a family of sets are known in advance, but which elements must be covered is revealed one element at a time, and each arriving element has to be covered at once by a set chosen irrevocably. The problem models resource placement under unknown…
Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers VII: Factor Model Fitting — the ADMM X-Update in Closed Form, Entry by EntryTextbook
Alternating direction methods are used when one part of an optimization problem is easy to minimize and another part has a simple projection. Chapter 9 of Boyd, Parikh, Chu, Peleato and Eckstein (2011) examines this idea with nonconvex constraints. Its examples include sparse vectors, Boolean vectors and low-rank matrices. The chapter says explicitly that…
On the Approximability of Single-Machine Scheduling with Precedence Constraints 2: Every Convex Bipartite Order Has a Realizer of Size 3Research Paper
The single-machine scheduling problem 1∣prec∣∑wjCj asks for an order in which to process n jobs, each with a processing time and a weight, on one machine, respecting a partial order of precedence constraints, so that the weighted sum of completion times is as small as possible. It is NP-hard, and the best known approximation ratio for…
From Predictive to Prescriptive Analytics 2: For Costs in [0, c̄] That Are L-Lipschitz, w.p. ≥ 1 − δ Every Decision Rule in F Costs ≤ Its Empirical Cost + c̄√(log(1/δ)/2N) + L·ℜ_N(F)Research Paper
Many operations decisions are made after observing side information: an inventory manager sees weather, search trends and calendar effects before ordering; a supply-chain planner sees market signals before shipping. Bertsimas and Kallus, in From Predictive to Prescriptive Analytics (arXiv:1402.5481v4, Management Science 2020), study how to turn such data…
Log-Barrier Interior Point Methods Are Not Strongly Polynomial 2: The Total Curvature of the Central Path of LW_r(t) Exceeds (2^(r−2) − 1)π/2 − ε for All Large tResearch Paper
Path-following interior point methods solve a linear program by tracking its central path, a smooth curve that runs through the interior of the feasible set and ends at an optimal solution. Their number of iterations is polynomial in the bit size of the input, and whether some interior point method is strongly polynomial (bounded by a polynomial in the…
On the Approximability of Single-Machine Scheduling with Precedence Constraints 3: The Incomparable-Pairs Graphs of Canonical Interval Orders Have Unbounded Chromatic NumberResearch Paper
Single-machine scheduling with precedence constraints asks for an order in which one machine processes jobs while respecting prescribed comparisons between them. For the objective of minimizing total weighted completion time, the structure of the precedence order can influence the quality of approximation algorithms. Ambühl, Mastrolilli, Mutsanas, and…
Regret in Decision Making under Uncertainty 2: With u(x, y) = x + f(x − y) and f Decreasingly Concave, the Same Decision Maker Takes a Fair Long-Odds Bet and Buys Fair InsuranceResearch Paper
Expected utility theory explains a single attitude toward risk by the curvature of a utility function of final wealth: a concave utility makes a decision maker risk averse, a convex one risk seeking. Several well documented patterns of behaviour do not fit this picture. The same people buy insurance against small-probability losses and buy lottery tickets…
On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems 3: With Uniform Hypercube Cost Uncertainty, the Robust Optimum Is at Least n + 1 Times the Stochastic OneResearch Paper
Many planning problems are made in two stages: a first decision x is fixed before an uncertain parameter is revealed, and a second decision y is taken afterwards. Two models compete for such problems. Two-stage stochastic optimization assumes a probability distribution over the scenarios and minimizes the expected cost, letting the second-stage decision…
Regret in Decision Making under Uncertainty 1: Under Assumptions 2 and 3, Utility over Final and Foregone Assets Takes the Regret Form u(x, y) = αv(x) + f(v(x) − v(y))Research Paper
Expected utility theory predicts that a decision maker's choice between two lotteries depends only on the distribution of final wealth under each. Observed behaviour contradicts this in systematic ways: the Allais paradox, the coexistence of insurance and gambling, and the reflection effect documented by Kahneman and Tversky (1979). David Bell's 1982 paper (…
Assortment Optimization under Variants of the Nested Logit Model 5: For General Nests, the Nested-by-Preference-and-Revenue LP Optimum Scaled by the Factor (12) Is Feasible for the Full LPResearch Paper
A retailer that groups its products into categories (brands, store sections, flight classes) and decides which products to display in each faces the assortment problem: offering more products attracts more customers but also diverts sales away from the most profitable products. The nested logit model is the standard description of customer choice in this…
Denumerable State Markovian Decision Processes—Average Cost Criterion: Every Limit Point of Policy Improvement Is a Deterministic Stationary Rule That Is Optimal over All RulesResearch Paper
Markovian decision processes with the long-run average cost criterion model systems run indefinitely: inventories, queues, maintenance schedules, communication links. For a finite state space the theory was settled by the early 1960s. Howard's policy improvement (policy iteration) procedure (1960) finds an optimal stationary rule in finitely many steps, and…
Optimality and Duality Theory for Stochastic Optimization Problems with Nonlinear Dominance Constraints 2: With Finite Scenarios and Slater's Condition, Piecewise-Linear Utilities Are MultipliersResearch Paper
Second-order stochastic dominance constraints let a decision maker require that a random outcome of a decision be preferred to a fixed benchmark outcome by every risk-averse expected-utility maximizer, without choosing a utility function in advance. Dentcheva and Ruszczyński introduced optimization under such constraints in Optimization with stochastic…
Maximum Pressure Policies in Stochastic Processing Networks I: Under the EAA Assumption, Maximum Pressure Is Pathwise Stable Whenever the Static Planning LP Has a Feasible Solution with ρ ≤ 1Research Paper
A processing network must decide which activities receive scarce processor capacity while jobs move among buffers. Such decisions matter in manufacturing, service systems, and switches: one activity can consume several processors at once, and a job can be routed to another buffer after processing. A policy that sees current buffer levels but does not need…
Contraction Mappings in the Theory Underlying Dynamic Programming 2: Under N-Stage Contraction and Monotonicity the Optimal Return Is the Unique Fixed Point of the Maximization OperatorResearch Paper
Infinite-horizon dynamic programs, including discounted Markov decision processes, stochastic games and semi-Markov models, are usually analysed through a single equation: the optimal return f solves the optimality equationv=Av, where A maximizes the one-step return over decisions. Denardo's 1967 paper (SIAM Review 9(2), 165–177) separated the argument…
Maximum Pressure Policies in Stochastic Processing Networks III: Strict Leontief Networks Satisfy the Extreme-Allocation-Available (EAA) AssumptionResearch Paper
A stochastic processing network (Harrison 2000) models a system in which processors carry out activities and each activity draws jobs from one or more buffers. Manufacturing lines, call centers with cross-trained agents, and data switches all fit this model. A central question is which scheduling policies are throughput optimal, meaning they stabilize the…
Coordinating Inventory Control and Pricing Strategies with Random Demand and Fixed Ordering Cost: The Finite Horizon Case 2: General Demand: Sym-k-Concave Profit-to-Go, Optimal (s, S, A, p) PolicyResearch Paper
A seller with replenishable inventory must decide how much to order and what price to charge before demand is known. A price that increases current revenue can also change the inventory left for later periods; a fixed charge for placing any positive order adds a discontinuity to the decision. Chen and Simchi-Levi study this coordination problem over a…
A Friendly Smoothed Analysis of the Simplex Method: Gaussian-Perturbed Shadows Have at Most 3 + 128πe²d²√(log n)σ⁻²(1 + 4σ√(d log n))(1 + 16σ√(log n)) Expected EdgesResearch Paper
The simplex method solves linear programs quickly in practice, yet for most pivot rules there are inputs on which it takes exponentially many steps (Klee and Minty, 1972). Smoothed analysis, introduced by Spielman and Teng (JACM 2004), explains the gap: it measures the expected running time when every constraint row of a worst-case input is perturbed by a…
The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs: Fully-Supported Problems Attain the Binomial Violation Tail ExactlyResearch Paper
Many design problems in control, finance and engineering are convex programs whose constraints depend on an uncertain parameter δ: a solution must satisfy x∈Xδ for every δ in a possibly infinite set Δ. Enforcing all constraints (robust optimization) is often intractable or overly conservative. The scenario approach draws N ind…
Convex Optimization: Algorithms and Complexity XVII: Goemans–Williamson Rounding of the MAXCUT SDP Relaxation Has Expected Value at Least 0.878 Times the Maximum CutTextbook
MAXCUT asks for a partition of the vertices of a weighted graph into two sets that maximizes the total weight of the edges between them. It is one of Karp's original NP-hard problems, so no polynomial-time exact algorithm is expected, and the natural question is how close a polynomial-time algorithm can come to the optimum. Sampling a uniformly random…