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.
Conditional Logit Analysis of Qualitative Choice Behavior 3: The Conditional Logit Likelihood Has a Maximum Exactly When No Direction Makes Every Observed Choice Weakly BestResearch Paper
The conditional logit model is the workhorse of discrete choice analysis in transportation, marketing, labour and industrial organization. McFadden's 1974 chapter derived it from a theory of population choice behaviour and showed how to estimate it by maximum likelihood; this line of work was recognized by his 2000 Nobel Prize in Economic Sciences, awarded…
Reversibility and Stochastic Networks IX: Partial Balance — Equivalent Characterizations via Truncation, Rate Changes and Time ReversalTextbook
Equilibrium distributions of Markov models of networks are rarely computed by solving the full equilibrium equations directly. In the classical product-form results (migration processes, Jackson and Kelly networks, loss networks, clustering processes) the equilibrium distribution satisfies a stronger, local family of equations, and that is what makes it…
Stochastic Optimal Control: The Discrete-Time Case VII: The Finite-Horizon Borel Model — over Universally Measurable Policies J*_K = T^K(J_0)Textbook
Finite-horizon stochastic control on general state and control spaces — inventory levels, queue lengths, positions, beliefs — cannot be written down without measure theory, and the measure theory turns out to be the hard part. The dynamic programming (DP) recursion "start from zero and minimise one stage at a time" is easy to state, but on uncountable…
A Primal–Dual Splitting Method for Convex Optimization Involving Lipschitzian, Proximable and Linear Composite Terms I: Iterates Converge Weakly to a Primal–Dual Solution When 1/τ − σ‖L‖² ≥ β/2Research Paper
Many convex optimization models combine a smooth loss, a nonsmooth penalty whose proximity operator is easy to compute, and a second penalty applied after a linear map. Imaging models, for example, often place a data-fitting term on the image and a regularizer on its transformed coefficients. The resulting objective has the form F(x)+G(x)+H(Lx). Condat's…
Conditional Logit Analysis of Qualitative Choice Behavior 2: Random Utility Maximizers Choose by Logit Exactly When Taste Shocks Are Extreme-Value DistributedResearch Paper
The conditional logit model assigns to an alternative i in a finite choice set the probability eVi/∑jeVj, where Vj is a "representative utility" built from observed attributes of the alternative and the decision maker. It is the workhorse of discrete choice econometrics, transportation demand forecasting, marketing and revenue management,…
Twice Regularized MDPs and the Equivalence Between Robustness and Regularization 2: The Greedy Policy of the R2 Optimal Value Is the Unique Optimal R2 PolicyResearch Paper
A robust Markov decision process (robust MDP) evaluates a policy against the worst transition kernel and reward in an uncertainty set around a nominal model (P0,r0). It is the standard model for planning when the dynamics are estimated from data (Iyengar 2005; Nilim and El Ghaoui 2005; Wiesemann, Kuhn and Rustem 2013). Its Bellman update contains an…
Reversibility and Stochastic Networks VIII: Markov Fields — A Positive Random Field Is Markov iff It Factorizes over the Simplices of the GraphTextbook
Many systems consist of a finite number of sites whose states influence one another only locally: fruit trees in an orchard that are diseased or healthy, power sources that are working or broken, individuals holding one of several views. Chapter 9 of F. P. Kelly, Reversibility and Stochastic Networks (Wiley, 1979) asks which joint distributions such systems…
Reversibility and Stochastic Networks V: Optimal Capacity Allocation in a Network of QueuesTextbook
Chapter 4 of F. P. Kelly's Reversibility and Stochastic Networks (Wiley, 1979) applies the product-form theory of Chapter 3 to concrete systems. Two of its results have numbered statements, and they answer two practical questions.
Projection-like Retractions on Matrix Manifolds II: The Metric Projection onto a C^k Submanifold Is Locally Unique and C^(k−1), so Projecting a Tangent Step Is a RetractionResearch Paper
Many optimization problems in statistics, signal processing and control are posed over sets of matrices with a constraint that makes them curved: matrices of fixed rank, matrices with orthonormal columns, symmetric matrices with a prescribed spectrum. Algorithms on such sets ("optimization on manifolds") compute a step in the tangent space at the current…
Reversibility and Stochastic Networks III: Open Networks of Queues with General Customer Routes Have Product-Form EquilibriumTextbook
Networks of queues model systems in which jobs visit a sequence of service stations: items in a manufacturing job-shop, packets in a communication network, patients moving between hospital departments. The open migration process of Chapter 2 of F. P. Kelly, Reversibility and Stochastic Networks (Wiley, 1979), and the job-shop networks of Jackson (Jackson…
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…