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.
Reversibility and Stochastic Networks IV: Symmetric Queues with Gamma-Mixture Service RequirementsTextbook
The classical product-form results for queueing networks (Jackson, Kelly, Baskett–Chandy–Muntz–Palacios) assume exponentially distributed service requirements, because then the state of a queue need not record how much service each customer has received. Real service times are rarely exponential: telephone call lengths, job sizes in time-shared computers…
The Best of Both Worlds: Stochastic and Adversarial Bandits: SAO Has Pseudo-Regret O(K log K log²β/Δ) on Stochastic Rewards and Regret Õ(√(nK)) Against Adaptive AdversariesResearch Paper
In a multi-armed bandit problem a learner chooses one of K actions in each of n rounds and observes only the reward of the chosen action. Two models of the rewards have separate theories. In the stochastic model, each arm pays independent draws from a fixed distribution; algorithms such as UCB1 (Auer, Cesa-Bianchi & Fischer 2002) have regret of order …
Approximation Algorithms for Stochastic Inventory Control Models 1: The Dual-Balancing Policy Costs at Most Twice the OptimumResearch Paper
Periodic-review inventory control with backorders is one of the basic models of operations research: in each period a manager decides how much to order, orders arrive after a lead time, unmet demand is backlogged at a penalty, and stock left over is charged a holding cost. When demands in different periods are independent, dynamic programming yields an…
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems I: Pseudo-Regret of (α, ψ)-UCBTextbook
The stochastic multi-armed bandit is the basic model of sequential decisions under uncertainty with partial feedback: a forecaster repeatedly picks one of K options and observes only the reward of the option it picked. It models clinical trials, ad placement, routing and dynamic pricing, and is the building block of many reinforcement-learning algorithms.…
Supply Chain Coordination with Revenue-Sharing Contracts: Strengths and Limitations 4: With Retailer Effort, the Supplier Prefers the Wholesale-Price Contract Exactly When τ > 1/√2Research Paper
A revenue-sharing contract{ϕ,w} lets a supplier charge a retailer a wholesale price w per unit and, in addition, collect the share 1−ϕ of the retailer's revenue. The video-rental industry adopted such contracts at scale in the late 1990s, and Cachon and Lariviere showed that in a broad class of models they coordinate the supply chain: the…
Linear Least-Squares Algorithms for Temporal Difference Learning I: Probability-One Convergence of Trial-Based LS TD on Absorbing Markov ChainsResearch Paper
Temporal-difference learning estimates the value of a policy from observed state transitions and rewards. In a finite Markov decision process, fixing a policy produces a Markov chain, so policy evaluation becomes the task of estimating the expected return from each state. Bradtke and Barto's 1996 paper introduced a least-squares temporal-difference method, L…
Dimensioning Large Call Centers IV: Asymptotically Optimal Staffing under a Waiting-Cost ConstraintResearch Paper
A call center has to decide how many agents to staff. In practice the decision is often posed as a service-level constraint rather than a cost trade-off: use the fewest agents for which the expected waiting cost, or the fraction of customers who wait, stays below a target. Borst, Mandelbaum and Reiman (CWI Report PNA-R0015, 2000; journal version in Operation…
The Sample Complexity of Pattern Classification with Neural Networks: The Size of the Weights is More Important than the Size of the Network III: Sigmoid Networks with Small Weights GeneralizeResearch Paper
A classifier built from a neural network produces a real score and predicts a binary label from its sign. A network can have many hidden units, so a guarantee based only on the number of parameters can be uninformative even when its output weights are small. Bartlett's 1998 paper asks whether a classifier's margin on training examples and the total…
Dimensioning Large Call Centers III: Asymptotically Optimal Staffing in the Quality-Driven RegimeResearch Paper
How many agents should a call center staff? Telephone call centers employ millions of people, and staffing is their largest cost, so the question is asked every half hour of every day (Gans, Koole & Mandelbaum, 2003). The classical model is the M/M/N (Erlang-C) queue: calls arrive at rate λ, service times are exponential with mean 1/μ, and N agents…
Supply Chain Coordination with Revenue-Sharing Contracts: Strengths and Limitations 2: With Competing Retailers, Revenue Sharing Supports the System-Optimal Quantities as a Nash EquilibriumResearch Paper
A supplier that sells through independent retailers usually loses part of the profit an integrated firm would earn: each retailer orders to maximize its own profit, not the channel's. Supply chain coordination asks which contracts make the decentralized choices coincide with the integrated optimum. Cachon and Lariviere study revenue-sharing contracts, under…
The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming 2: Under Remotest-Set Control Every Limit Point Is CommonResearch Paper
Many problems in optimization, image reconstruction and statistics reduce to the convex feasibility problem: given closed convex sets Ai, i∈I, find a point of their intersection R=⋂i∈IAi. A classical approach is the relaxation method: from the current point, move to the nearest point of one of the sets, and repeat. For Euclidean distance…
Stochastic Optimal Control: The Discrete-Time Case II: Contraction Models — the Optimal Cost Is the Unique Fixed Point of T in the Closed Set B̄Textbook
Discounted dynamic programming with bounded cost per stage is the standard setting in which infinite-horizon sequential decision problems are well posed: the optimal cost exists, satisfies Bellman's equation, and can be computed by iterating the DP operator. Shapley proved this for stochastic games in 1953 (Shapley 1953), Blackwell for discounted Markov…
Dimensioning Large Call Centers II: Asymptotically Optimal Staffing in the Efficiency-Driven RegimeResearch Paper
A call center must choose enough servers to limit waiting while paying for every server it staffs. When arrivals are heavy, small changes in the number of servers can change the probability of delay substantially. Borst, Mandelbaum, and Reiman study how to make this choice when the arrival rate grows and the costs of staffing and waiting need not grow at…
Variance-based Regularization with Convex Objectives IV: Fast Rates for Approximate Robust Minimizers under a Growth ConditionResearch Paper
In stochastic optimization and statistical learning one chooses a parameter θ from a set Θ⊆Rd to make the riskR(θ)=EP[ℓ(θ;X)] small, having seen only a sample X1,…,Xn from P. Generalization bounds suggest trading empirical risk against its standard deviation, but the variance-penalized objective is…
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization 2: Randomized Double Greedy Achieves 1/2 of the Optimum in ExpectationResearch Paper
Many selection problems assign a value to each subset of a finite collection: the coverage supplied by chosen facilities, the influence reached by chosen seeds, or the value of a coalition. A submodular set function has diminishing returns in the precise sense that the combined value of two sets, counting their overlap once, does not exceed the sum of their…
Dynamics of Stochastic Approximation Algorithms 4: Subgaussian Martingale Noise with Σ exp(−c/γ_n) < ∞ for Every c > 0 Satisfies Assumption A1 Almost SurelyResearch Paper
A stochastic approximation algorithm is a recursion
Stochastic Optimal Control: The Discrete-Time Case VI: Lower Semianalytic Functions — Analytically Measurable ε-Optimal Selectors (Jankov–von Neumann)Textbook
Dynamic programming over uncountable state and control spaces needs two things at every stage: the optimal cost-to-go, obtained by minimizing over the control, must be a function that can be integrated against the next stage's transition probabilities, and a policy that nearly attains the minimum must be measurable, so that it defines a stochastic process.…
Supply Chain Coordination with Revenue-Sharing Contracts: Strengths and Limitations 1: Revenue Sharing at w = φc Coordinates the Channel and Gives the Retailer the Share φ of Its Optimal ProfitResearch Paper
A supplier who sells to an independent retailer through a plain per-unit wholesale price faces double marginalization: the retailer orders less than the quantity that maximizes the profit of the supply chain as a whole, because each unit costs him the wholesale price rather than the production cost. Supply chain contracting studies payment schemes under…
The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming 1: Under Cyclic Control Every Limit Point Is a Common PointResearch Paper
Many problems in optimization and numerical analysis reduce to finding a point in the intersection of finitely many closed convex sets: solving a system of linear equations or inequalities, reconstructing an image from projections, or finding a feasible point of a convex program. The classical methods for this convex feasibility problem project the current…
Stochastic Optimal Control: The Discrete-Time Case V: Semicontinuous Functions — a Borel-Measurable Minimizing Selector for Lower Semicontinuous CostsTextbook
Every step of the dynamic programming algorithm on a general state space does three things: it takes a conditional expectation of the cost-to-go under a transition kernel, it minimizes the resulting function of state and control over the control, and, if a policy is to be produced, it picks a control for each state that attains or nearly attains that…
The Price of Stability for Network Design with Fair Cost Allocation I: The Price of Stability of Fair Cost Sharing Is at Most H(k), and This Is TightResearch Paper
Many networks are built and paid for by the users they serve: multicast trees, virtual overlays, shared subnetworks of the Internet. A protocol proposes a design and a rule for splitting its cost, and each participant is free to accept the proposal or defect to a cheaper alternative. The designer therefore cannot impose the global optimum; the best it can…
Mean Field Games: Numerical Methods for the Planning Problem I: The Discrete Planning Scheme Has a Solution, Given by a Fenchel–Rockafellar Saddle PointResearch Paper
Mean field games (Lasry and Lions, 2006–2007; Huang, Malhamé and Caines, 2006) model the limit of a large population of identical rational agents. Each agent solves an optimal control problem whose cost depends on the distribution m of all agents, and the distribution is in turn transported by the agents' optimal feedback. In the continuous setting this…
Variance-based Regularization with Convex Objectives II: A Covering-Number Certificate and Oracle Inequality for the Robust MinimizerResearch Paper
Empirical risk minimization (ERM) chooses, from a class F of loss functions, the one with the smallest average loss on a sample X1,…,Xn. Its standard guarantees bound the excess population risk by a term of order 1/n, whatever the variance of the losses. When good functions in F have small variance, a better trade-off is…
Two Theorems in Graph Theory: A Matching Is Maximum If and Only If No Alternating Chain Joins Two Neutral PointsResearch Paper
A matching of a graph is a set of edges no two of which share a vertex. A matching with as many edges as possible is a basic object of combinatorial optimization. Assignment problems, pairing and scheduling problems, and the Chinese postman problem reduce to it, and it is the standard example of a problem with a polynomial-time algorithm that is not an…
Approximation Algorithms for Stochastic Inventory Control Models 2: The Triple-Balancing Policy Costs at Most Three Times the Optimum for Stochastic Lot-SizingResearch Paper
Periodic-review inventory control with a fixed ordering cost is one of the oldest problems in operations research. A firm reviews its stock at the beginning of each of T periods, decides whether to place an order, pays a fixed cost K for every order it places, and pays holding costs on leftover stock and penalties on unmet (backlogged) demand. When demand…