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.
Multi-product Dynamic Pricing with Limited Inventories under a Cascade Click Model: The Cascade Correction Policy Loses O(logk) Against the Deterministic BenchmarkResearch Paper
Online retailers show products in a fixed order, and a customer reads the list from the top. Models of this behavior, the cascade click model, come from sponsored search (Craswell et al., 2008; Aggarwal et al., 2008) and now drive assortment and ranking decisions. Najafi, Duenyas, Jasin and Uichanco combine it with the classical problem of pricing a limited…
Taylor Approximation of Inventory Policies for One-Warehouse, Multi-Retailer Systems with Demand Feature Information: The TA Policy Is Asymptotically Optimal in the Number of RetailersResearch Paper
Retail chains that run a central warehouse and many stores must commit to a warehouse replenishment quantity before they know how much each store will need, and then split the delivered stock among the stores once more information arrives. This is the one-warehouse, multi-retailer (OWMR) distribution problem, a classical model of multi-echelon inventory…
Learning-based Robust Optimization: Procedures and Statistical Guarantees: with n₂ ≥ log δ/log(1 − ϵ), the data-split order-statistic set covers 1 − ϵ of P with confidence 1 − δResearch Paper
A chance-constrained program (CCP) asks for a decision x minimizing a cost f(x) subject to
P(g(x;ξ)∈A)≥1−ϵ, where ξ is a random parameter with law P and ϵ is a
tolerance level. Chance constraints model reliability requirements in operations, finance and
engineering, but they are hard to solve: the feasible set is usually nonconvex,…
Processing Networks XVII: A Relative-Entropy Lower Bound for the Traffic Equations of a Transient Routing MatrixTextbook
In a multiclass processing network, jobs of class i arrive from outside at rate λi and, after service, move to class j with probability Pij or leave the network. The traffic equationsα=λ+P′α give the total arrival rate αi into each class. Chapter 10 of Dai and Harrison's Processing Networks: Fluid Models and Stability proves…
Stability of Procurement Networks: A Network Is Rationalizable as Pairwise Stable with k-Anonymous Preferences If and Only If It Satisfies k-WARPSResearch Paper
Procurement data record who buys from whom: public agencies and their contractors, manufacturers and their tier-1 and tier-2 suppliers. A basic question about such a network is whether it is stable, meaning that no firm would drop an existing relationship and no pair of unlinked firms would jointly gain from forming one. The standard notion is pairwise…
The Value of Observing the Buyers’ Arrival Time in Dynamic Pricing: Observing the Buyer’s Arrival Raises the Seller’s Optimal Revenue by a Factor of at Most 4.911Research Paper
A retailer who sells a seasonal good over time faces customers who know that prices may fall and who time their purchases strategically. A large operations literature studies how a seller should set a price path against such forward-looking buyers (for example Besanko and Winston, 1990; Aviv and Pazgal, 2008; Cachon and Swinney, 2009). A basic informational…
Sampling from the Gibbs Distribution in Congestion Games: Relaxed Logit Dynamics in Extension Parallel Congestion Games Mix within n3(log(nlog∣P∣+TΦmax)+log(1/(2ϵ2))) StepsResearch Paper
Logit dynamics is the standard model of noisy best-response play: repeatedly, a uniformly random player revises their strategy, choosing each option with probability proportional to e−T⋅cost, where the temperatureT≥0 measures rationality. In a potential game the dynamics is a reversible Markov chain whose stationary law is the Gibbs…
How Does Risk Hedging Impact Operations? Insights from a Price-Setting Newsvendor Model: When the Asset Trend Raises Demand, Hedging Lowers the Optimal Price and Virtual Production QuantityResearch Paper
Manufacturers whose demand moves with a traded asset (automakers with oil prices, airlines with fuel, exporters with exchange rates) can trade that asset continuously while they set prices and production. Whether such financial hedging should change operational decisions, and in which direction, is a question operations management has asked since Gaur and…
A Theory of Alternating Paths and Blossoms from the Perspective of Minimum Length: Max-Level Paths Contain a Bridge, Bases Are Unique and Blossoms Are Laminar at Every Eligible TenacityResearch Paper
A matching in a graph is a set of edges no two of which share a vertex. Maximum-cardinality matching is one of the basic problems of combinatorial optimization, and the fastest known algorithm for it in general graphs is the Micali–Vazirani (MV) algorithm (Micali–Vazirani, FOCS 1980), which runs in O(mn) time. It follows the phase structure of…
An Equivalent Reformulation and Multi-Proximity Gradient Algorithms for a Class of Nonsmooth Fractional Programming: Under the KL Property, the Iterates of CMPGA_ML Converge to a Critical PointResearch Paper
Many models in signal processing and statistics minimize a ratio of two functions. A prominent family is scale-invariant sparse recovery: the L1/L2 model minimizes ∥x∥1/∥x∥2+2λ∥Ax−b∥22 over a box, and the L1/SK model divides ∥x∥1+2λ∥Ax−b∥22 by the sum of the K largest entries of ∣x∣ (Rahimi–Wang–Dong–Lou, SIAM J.…
A New Homotopy Proximal Variable-Metric Framework for Composite Convex Minimization: Global Linear Convergence of the Exact Homotopy Scheme under Strong Convexity and Lipschitz GradientResearch Paper
Composite convex problems minxf(x)+g(x), with f smooth and g nonsmooth, cover the regularized estimation and constrained models of statistics, signal processing and machine learning. Proximal variable-metric methods (Lee, Sun and Saunders, 2014) solve them with a metric that adapts to the curvature of f, but each step is a scaled proximal subproblem,…
Rockafellian Relaxation and Stochastic Optimization under Perturbations: Under Strict Limiting Exactness, Cluster Points of Approximate Minimizers of Approximating Problems Solve the Actual ProblemResearch Paper
Many optimization problems are posed with data that are known only approximately: a probability distribution estimated from biased samples, a model calibrated on corrupted measurements, a constraint whose right-hand side will shift. Solving the problem with the on-hand data and hoping for the best can fail badly. The paper's opening examples (§2) show that…
Multi-armed Bandit Experimental Design: Online Decision-making and Adaptive Inference: EXP3EG Estimates Every Treatment Effect Within 4(2+2K2(1+e2))log(2/δ)/t1−α with Probability 1−δResearch Paper
An online experiment has two audiences. The experimenter who cares about welfare wants to stop assigning people to inferior treatments as quickly as possible; the statistician wants an accurate estimate of how much better one treatment is than another. A multi-armed bandit policy serves the first and starves the second: an arm that is played rarely is…
Maximal Objectives in the Multi-armed Bandit with Applications: ADA-ETC Has an Explicit Instance-Dependent Regret Bound and Worst-Case Regret O(K^{1/3}T^{2/3}√log K) for the Max ObjectiveResearch Paper
In the classical stochastic multi-armed bandit, a decision-maker pulls one of K arms at each of T times and is judged by the sum of all rewards collected. Ozbay and Kamble (arXiv:2006.06853v6, later in Management Science, 2024) study a different objective: the decision-maker is judged by the largest cumulative reward of a single arm at the end of the…
Efficiency of Stochastic Coordinate Proximal Gradient Methods on Nonseparable Composite Optimization: With Probability ≥ 1 − e^{−β²(1−δ)(K+1)/2}, min_{i≤K} ‖∇F(xᵢ)‖² ≤ (F(x₀) − F*)/(C(1−β)(1−δ)(K+1))Research Paper
Many problems in machine learning, signal processing and control minimize a composite objective F(x)=f(x)+ψ(x) over x∈Rn. Here f is smooth and ψ is a regularizer or penalty. When n is large, a full gradient or a full proximal step costs too much, and coordinate descent methods update only a few coordinates or a low-dimensional subspace per…
Stochastic Comparative Statics in Markov Decision Processes: The Policy Function and the Expected Decisions in All Future Periods Increase with the Discount Factor and Complementary Payoff ParametersResearch Paper
Dynamic programs in operations research and economics are routinely used to ask comparative statics questions: when a parameter of the model increases, does the optimal decision increase? For Markov decision processes the classical answer, going back to Topkis (1978) and his book Supermodularity and Complementarity (1998, cited by the paper as Topkis…
Data-Driven Sample Average Approximation with Covariate Information: The Empirical Residuals-Based SAA Is Consistent and Asymptotically OptimalResearch Paper
Many decisions under uncertainty are taken after observing side information. A retailer orders stock knowing the season and the weather forecast; a grid operator commits generation knowing the time of day and the wind forecast. The decision maker wants to solve the conditional stochastic program
Assortment Optimization with Multi-Item Basket Purchase under Multivariate MNL Model: Without Interaction Terms, Algorithm U1 Finds a (1 − ε)-Optimal Assortment in Polynomial TimeResearch Paper
Retailers rarely sell one item at a time. A shopper fills a basket with, say, one book, one film and one game, and the decision to buy in one category is linked to the others: if nothing in the store is attractive enough, the shopper leaves without buying anything. Assortment optimization asks which products a retailer should offer so as to maximize…
When Yield Is Not the Only Supply Uncertainty: Newsvendor Model of a Trade Agent: The Optimal Bid Is Unique, and Zero Exactly When the Expected Sales-to-Supply Ratio Is at Most h/ρResearch Paper
A trade agent buys a product from a seller and resells it to a buyer whose demand D is fixed by contract. Agricultural produce, surplus inventory and commodities are often traded this way: the agent owns no warehouse, so units it buys beyond the demand must be disposed of, and demand it cannot serve incurs a contractual penalty. The agent's only lever is…
Data-Driven Minimax Optimization with Expectation Constraints: Basic-CSPD Attains the O(1/√N) Rate for the Objective Gap and Feasibility ResidualsResearch Paper
Stochastic minimax problems minx∈Xmaxy∈YEω[f(x,y,ω)] arise in robust optimization, AUC maximization, games and adversarial training. Projected stochastic gradient descent–ascent solves them when projections onto X and Y are cheap. In data-driven applications the feasible sets are often…
Prophet Inequality for Bipartite Matching: Merits of Being Simple and Nonadaptive: Static Vertex Prices Earn One Third of the Prophet's Expected Matching ValueResearch Paper
A prophet inequality compares an online decision maker, who sees random values one at a time and must decide irrevocably, with a prophet who sees every value in advance. The classical single-item version (Krengel–Sucheston, Samuel-Cahn) shows that a single threshold earns half of the prophet's expected maximum. These guarantees are the analytic core of poste…
Langevin Dynamics Based Algorithm e-THεO POULA for Stochastic Optimization Problems with Discontinuous Stochastic Gradient: Non-Asymptotic Bound on the Expected Excess RiskResearch Paper
Many stochastic optimization problems in machine learning, finance and insurance minimize an expectation u(θ)=E[U(θ,X)] whose stochastic gradient is discontinuous in the parameter: quantile estimation, vector quantization, CVaR minimization and networks with ReLU activation all have this form. The objective may also be non-convex, and its gradient…
Optimal Policy for Inventory Management with Periodic and Controlled Resets: Under the Discount-Factor Bound (29), a Four-Threshold (σ, s, S, Σ) Reset-and-Order Policy Is OptimalResearch Paper
Many stocked goods can be thrown out and restarted: a water reservoir that becomes contaminated, a product line that is replaced, perishable stock that is discarded. In each case a manager decides each period how much to order and also whether to reset, that is, discard the whole stock and start again from empty. Lee, Mintz, Aswani, Shen and Yang (arXiv:2209…
Unichain and Aperiodicity Are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits: The Set-Expansion Policy Has Optimality Gap at Most 256 r_max λ_W²|S|²/(β²√N)Research Paper
A restless bandit couples N identical Markov decision processes through a budget: at every time step exactly αN of the N arms must be pulled, and every arm changes state whether it is pulled or not. The model, introduced by Whittle (1988), describes scheduling of machines or patients, sensor management, queueing control and recommendation. Computing…
Online Resource Allocation under Partially Predictable Demand: The Non-Adaptive Threshold Algorithm Is p + (1−p)/(2−a) − O(√(log n / b)/(a(1−p)p)) CompetitiveResearch Paper
A firm sells b identical units over n periods. In each period at most one customer arrives, pays 1 (type 1) or a∈(0,1) (type 2), and must be accepted or rejected on arrival. This two-fare problem is the basic model of revenue management and of online resource allocation (advertising budgets, hotel rooms, cloud capacity). Two arrival models dominate its…