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.
Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments VI: Revenue-Ordered Offer Sets Grow with Capacity Left and Shrink with Time LeftResearch Paper
In airline and hotel revenue management a firm sells a fixed stock of a perishable resource (seats on a flight leg, rooms on a night) over a finite selling horizon, and in each period decides which fare classes to open. Customers do not buy a fixed fare: they choose among the fares on offer, or leave. Talluri and van Ryzin (Management Science, 2004)…
Supply Chain Coordination with Contracts II: With Price-Dependent Demand the Price-Contingent Buy-Back Gives the Retailer λΠ(q, p), as Revenue Sharing Does, and Coordinates Price and QuantityTextbook
A retailer who controls both inventory and price can respond to a supply contract in two ways. A contract that induces the right order quantity at a fixed price may change the retailer's incentive to raise or lower that price. For a one-season supply chain, Cachon's chapter compares familiar contracts under price-dependent demand and identifies a…
Send-and-Split Method for Minimum-Concave-Cost Network Flows I: A Minimum-Cost Flow Exists iff Every Simple Circulation Has Nonnegative Cost, and Then an Extreme One Exists (Theorem 1)Research Paper
Many network design and production–distribution problems have economies of scale: shipping twice as much along an arc costs less than twice as much, because of fixed charges, set-up costs or volume discounts. Modelled as network flows, such problems ask for a flow of least cost when each arc cost is a concave function of the flow on the arc. Classical…
Finding Minimum-Cost Circulations by Successive Approximation II: For Real Costs, the Strongly Polynomial Loop Reaches a Minimum-Cost Circulation After at Most m⌈log₂(2n)⌉ RefinementsResearch Paper
A minimum-cost circulation is a way to send flow around a directed network while respecting capacities and paying a cost per unit on each arc. It is a basic form of network optimization: a minimum-cost flow with prescribed supplies and demands can be reduced to a circulation problem, and the circulation formulation exposes the residual arcs on which a flow…
Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach 1: The f-Divergence Robust Mean Is the Sample Mean plus √(ρ·s_n²/n) up to o(n^(−1/2)) Almost SurelyResearch Paper
Distributionally robust optimization replaces the average of a loss over a sample by its worst-case average over all distributions close to the sample. When closeness is measured by an f-divergence, the worst case over a ball of radius ρ/n around the empirical distribution is also the upper endpoint of a generalized empirical likelihood confidence…
Online Stochastic Matching: Beating 1-1/e 3: No Online Algorithm Beats Expected Approximation Factor 26/27 on a 6-Cycle, and None Reaches 1 − o(1) on Disjoint 6-CyclesResearch Paper
Online bipartite matching asks an algorithm to assign arriving requests to resources it cannot reassign later. In display advertising, the requests are page views (impressions) and the resources are advertisers who have bought a fixed number of impressions in advance; each impression must be served immediately or lost. In the adversarial model, Karp,…
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…