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.
Error Analysis of Surrogate Models Constructed through Operations on Sub-models: a product of n models exact at x0 has Hessian accuracy of order min{Nig,Nih} with constant KFh(x0)Research Paper
In derivative-free and blackbox optimization, the objective can often be evaluated but not differentiated, and algorithms work with surrogate models built from function values. Their convergence theory depends on how accurate those models are. Conn, Scheinberg and Vicente codified this through fully linear and fully quadratic models; a fully linear class…
Signaling Service Quality Through Queue Disclosure: with uninformed customers, the unique pure perfect sequential equilibrium pools on concealment below λ^, on revelation above itResearch Paper
Whether a service provider should show customers its queue is a classical question in the economics of queues. When customers know the quality of service, the answer is a threshold in market size: Hassin (1986) and Chen and Frank (2004) showed that a revenue-maximizing server conceals the queue when the potential arrival rate is small and reveals it when it…
Joint Estimation and Robustness Optimization: Support functions of estimate uncertainty sets via convex conjugatesResearch Paper
An optimization model often takes an estimated parameter as if it were known exactly. A decision that performs well at that estimate can perform poorly at another parameter value that fits the observations almost as well. Joint estimation and robustness optimization connects these two tasks by constructing the uncertainty set from the estimation procedure…
Adjustable Robust Optimization Reformulations of Two-Stage Worst-Case Regret Minimization Problems: Exact reformulation of absolute regret with objective uncertaintyResearch Paper
A planner who commits resources before learning their eventual returns can evaluate a decision by how much better another decision would have performed after those returns became known. This absolute regret criterion compares against the best feasible hindsight decision under the same realization of uncertainty. It differs from protecting only the lowest…
Is Q-learning Provably Efficient?: Q-learning with UCB-Bernstein achieves near-optimal regretResearch Paper
Q-learning maintains estimates of the reward obtainable from each state and action. This makes it a natural method when an agent can interact with an environment but cannot ask a simulator for arbitrary transitions. The central question is whether these local value updates can support a quantitative guarantee on the reward lost during exploration. Jin,…
Distribution-Free Inventory Risk Pooling in a Multilocation Newsvendor: Tight worst-case cost for two locationsResearch Paper
A retailer with stock at several locations can serve a customer from a nearby location when local inventory runs out. This flexibility reduces shortages, but shipping and unused inventory still cost money. Evaluating the benefit requires a joint demand distribution: high demand at one location is easier to absorb when demand elsewhere is low. In practice, a…
Blockchain-Enabled Deep-Tier Supply Chain Finance: Optimal direct financing and universal blockchain adoptionResearch Paper
A manufacturer can have ample cash while an upstream supplier lacks the funds needed to make production reliable. Financing that supplier through an intermediary changes both the cost of credit and the incentives to invest. Information is also uneven: a firm may know its immediate supplier's working capital without knowing the capital of a more distant…
Finite-State Contract Theory with a Principal and a Field of Agents: Optimal contracting as McKean–Vlasov controlResearch Paper
A principal may influence a population by offering payments tied to each individual's observed history. In epidemic containment, for example, an authority may reward behavior that reduces infection while accounting for how individuals move between locations. The principal must anticipate both each individual's response and the population distribution…
The Price of Robustness: Tight probability bounds for symmetric uncertaintyResearch Paper
A linear optimization model can prescribe a decision that uses nearly all available capacity. If the coefficients measuring resource consumption are uncertain, even a small change can make that decision infeasible. Protecting against every simultaneous adverse change can instead sacrifice a substantial amount of the nominal objective. Budgeted robustness int…
Supply Chain Inventory Management and the Value of Shared Information: A lower bound on costs under every feasible policyResearch Paper
A supplier receiving orders from several retailers sees only part of the demand that drives the supply chain. Access to the retailers' inventory and demand histories can change when the supplier orders and where it sends available stock. A comparison between two selected policies, however, does not establish how much an unknown better policy could save. A po…
A Nonparametric Algorithm for Optimal Stopping Based on Robust Optimization: Existence and finite characterization of optimal robust stopping rulesResearch Paper
An exercise decision can depend on today's observed state even when the evolution of that state depends on its history. Examples include deciding when to exercise an option whose reward depends on several asset prices or on earlier observations. A simulator can produce complete trajectories without providing the conditional distributions needed for a…
ALSO-X and ALSO-X+: Better Convex Approximations for Chance Constrained Programs: ALSO-X is at least as good as CVaRResearch Paper
A chance constrained program chooses a decision before observing uncertainty and limits the probability that its constraints fail. For example, a service system can allow a prescribed fraction of demand realizations to exceed its available capacity. The optimization problem combines a cost objective with a probability requirement. Even when each realized…
Assortment Optimization for a Multistage Choice Model: Revenue-ordered and nested optimal assortmentsResearch Paper
A seller may offer one catalog of products now and a different catalog later. A customer's first purchase can determine which products become available in the second stage. An airline ticket followed by an upgrade offer is one example. When customers anticipate those later offers, changing a continuation assortment can change demand in the first stage as…
Distributionally Robust Inventory Control When Demand Is a Martingale: Closed-form minimax policy, worst-case demand and optimal valueResearch Paper
An inventory manager orders before seeing demand. Unsold stock incurs a holding cost, while unmet demand remains as a backlog and incurs a shortage cost. When the full demand distribution is unknown, a policy can be evaluated by its largest expected cost among distributions consistent with the available information. Dependence across periods matters because…
Optimizing Free-to-Play Multiplayer Games with Premium Subscription: Optimal advertising and subscription pricingResearch Paper
A free-to-play multiplayer game earns subscription revenue only if players value the premium experience enough to pay for it. Yet converting free players into premium players also changes the experience of everyone else. Premium players may enjoy owning items that others lack, while free players may dislike comparisons with premium players. Advertising…
Technical Note—Joint Learning and Optimization of Multi-Product Pricing with Finite Resource Capacity and Unknown Demand Parameters: Rate-optimal regret of PSCResearch Paper
A seller offering several products often shares resources across those products. A room-night can support several travel packages; a seat can serve several itineraries. Selling one product changes what remains available for future customers. When the seller does not know how purchase probabilities respond to prices, each decision also determines what can be…
Joint Learning and Optimization for Multi-Product Pricing (and Ranking) Under a General Cascade Click Model: The regret bound for UCB-CascadeResearch Paper
A seller displaying several products must learn more than the probability of a sale. A low purchase rate can reflect customers leaving before reaching a product, declining to click, or clicking and then deciding against purchase. These mechanisms matter because changing an early product's price changes both its sales and the number of customers who reach…
Multimodal Dynamic Pricing: High-probability regret for smooth multimodal demandResearch Paper
A retailer learning demand must choose prices before knowing which price earns the most. Each sale provides information only at the price actually posted. A demand curve can have several locally attractive regions, so a method that searches near one apparent optimum can overlook a better region. Wang, Chen and Simchi-Levi study pricing under smoothness…
Distributionally Robust Markov Decision Processes: S-robust strategies are distributionally optimal and admit a saddle pointResearch Paper
A planner who controls a stochastic system often knows more than a range of possible transition probabilities, but less than a complete probability distribution for those probabilities. For example, a small confidence region may contain a parameter with probability at least 90%, while a larger region contains it with certainty. Optimizing against every…
Production Planning by Mixed Integer Programming V: Intersecting Constant-Capacity Lot-Sizing HullsTextbook
A production plan must meet demand on time while deciding which periods justify a setup. When each active period can supply at most the same amount, the capacity limit links setup decisions to cumulative demand. A linear relaxation that treats those decisions as fractional may admit plans that cannot be assembled from feasible binary setup schedules.…
Production Planning by Mixed Integer Programming III: The Wagner–Whitin Convex HullTextbook
A production planner must meet demand over several periods while deciding when to incur fixed setup costs. Producing early can combine several periods into one batch, but the resulting inventory carries a holding cost. Even for one item without a capacity limit, continuous production quantities interact with discrete setup decisions. An exact linear…
Production Planning by Mixed Integer Programming I: Facility Location Reformulation of Uncapacitated Lot-SizingTextbook
Production planning combines continuous quantities with discrete decisions about when a machine is prepared to produce. A setup can incur a fixed charge even when the amount subsequently produced is small. Relaxing the setup decision to a fraction can therefore give a cost bound that is too optimistic. For a single product without capacity limits, a…
Price Discrimination with Fairness Constraints: Welfare effects of a little fairnessResearch Paper
A seller can charge different customer groups different prices when their willingness to pay differs. Limiting that discrimination changes both the seller's profit and what buyers receive. Equal prices are one possible fairness objective; equal purchase probabilities, equal consumer surplus and equal valuations among non-buyers express different concerns.…
On the Closest String and Substring Problems: A Random-Sampling PTAS for Closest Substring, Within Factor 1 + 1/(2r−1) + 3εr of Optimal with Probability 1 − 2(nm)^(−1/3)Research Paper
Many tasks in computational biology ask for a short pattern that occurs, with few errors, in each of a family of DNA or protein sequences: locating binding sites, finding conserved regions in unaligned sequences, designing PCR primers and genetic probes, and searching for a drug sequence that binds to a set of pathogen genomes. With Hamming distance as the…
Driver Surge Pricing: Prices m_iτ + z_i q_{i→j}(τ) Make Accepting Every Trip the Unique Optimal Driver Policy When R1/R2 ∈ (C, 1), and Accepting All Surge Trips Optimal for Every R1 < R2Research Paper
Ride-hailing platforms pay drivers per trip, and drivers are free to decline requests. When demand fluctuates, a trip accepted now also decides where and when the driver will be free next. During a surge (a period of high demand and high pay) a long trip keeps a driver busy after the surge may have ended, so a driver may rationally decline trips the…