CS Paper Radar

Improved Asymptotic Approximation Guarantees for Continuous-Review Lost-Sales and Dual-Sourcing Inventory Models

Weitian Tong, Yao Xu

cs.DS ·submitted 2026-11-18 18:32 UTC · v1
benchmark

Abstract

We study continuous-review inventory models with unit Poisson demand and deterministic lead times: single sourcing with lost sales and dual sourcing with backlogging. Xin [Operations Research. 70(1):111--128 (2022)] establishes an asymptotic approximation factor of 1.79 for each model in its proportional-growth regime. Under the same assumptions, we obtain a factor of 1.248977 for the better of base-stock and constant-order policies for lost sales and a factor of 1.599528 for the better of dual-index and tailored base-surge policies for dual sourcing. The benchmark is the optimal long-run average cost over all policies using only current and past information. For lost sales, lead time and the lost-sales penalty grow proportionally. For dual sourcing, the lead-time difference grows proportionally to the express premium, the extra unit cost of faster supply, while express lead time and backorder penalty remain fixed. For sufficiently large fixed backorder penalties, the dual-sourcing factor improves to 1.248977. The improvements follow from stronger lower bounds on the optimal cost. We retain intermediate constraints on mean inventory for lost sales and use events determined only by future demand to bound backlog costs for dual sourcing.

Comment
38 pages

Closest papers

Nearest neighbours by meaning across the whole index.

SabreAgent: Language Models at Design Time for Lost-Sales Inventory Control

cs.CE ·2026-09-17 ·Yang Liu, Yulin Huang, Xue Yu, Jiong Dong, Jianshen Zhang +1 more
benchmark similarity 0.66
Abstract · 36 pages, 6 figures

SabreAgent uses a language model at design time to construct two components for lost-sales inventory control: a product-specific seasonal prior and a validation-selected capped base-stock policy family. During operation, statistical forecasting and inventory optimization use these frozen artifacts to determine orders, with zero language-model calls. We evaluate the approach on the $1{,}320$ instances of InventoryBench. Under the benchmark's cost assumptions, the operations-research core draws on a zero-lead-time optimality result and a projected-inventory rule for positive deterministic lead times. The latter computes replenishment shortfalls by propagating inventory using sales along simulated demand paths. The seasonal prior adds forecast variants alongside the original forecaster, and the selected policy family handles stochastic lead times with order destruction. SabreAgent scores $0.6311$, compared with $0.5380$ for the strongest published baseline, and ranks first in all six benchmark cells. Ablations attribute most of the gain to the OR core. In the paired analysis, the seasonal component adds $1.79\%$ across the three real-data cells, and the search component adds $2.3\%$ across the two stochastic-lead-time cells. These results demonstrate how model-generated priors and policy structure can improve an OR controller through design-time use.

0.18

A 5/3 Guarantee for Echelon Stock (R,nQ) Policies in Two-Stage Stochastic Serial Systems

cs.DS math.OC ·2026-09-06 ·Ming Hu
benchmarktheory similarity 0.66
Abstract · 32 pages of main text and references, plus a 32-page online appendix; 6 figures

Fixed shipment costs encourage large orders, while inventory and customer backlog costs favor frequent replenishment. In a serial system, the stages must also coordinate their lot sizes and material availability. We study the classical echelon stock $(R,nQ)$ policy: the downstream stage requests a fixed lot, the upstream stage orders an integer multiple of that lot, and transfers contain complete lots. For unit Poisson demand, deterministic lead times, setup and holding costs at both stages, and full backlogging, we prove that the optimized cost in this class is at most $5/3\approx1.667$ of the optimal admissible system cost, uniformly over all nonnegative cost rates, demand rates, and lead times. The guarantee holds even when the selected policy pays a setup charge for every lot while the optimal benchmark pays only once per aggregate shipment. To obtain the guarantee, we use a common inventory calculation that allows independently chosen replenishment frequencies while respecting upstream material availability. We compare its optimized value, an upper bound on the best integer-ratio policy cost, with a novel lower bound on the optimal system cost that combines allocated single-stage costs with the minimum inventory cost when setup costs are zero. We also show that no uniform factor below $(1+\sqrt{3})/2\approx1.366$ is possible for the classical class. Existing numerical experiments place best-found classical policies within $22.7\%$ of an evaluated lower bound across three broad grids. The results quantify both the reliability and the limits of a simple operating rule and explain how shipment consolidation, replenishment timing, and flexibility affect its value.

0.26

Improved Approximation Guarantees for Periodic-Review Stochastic Inventory Control

cs.DS math.OC ·2026-10-30 ·Danny Segev
benchmark similarity 0.64
Abstract

In periodic-review stochastic inventory control, replenishment policies must balance holding and backlogging costs while responding to uncertain demands and evolving forecasts that may be arbitrarily correlated and nonstationary. In this general information setting, Levi, P{á}l, Roundy, and Shmoys (Mathematics of Operations Research 2007) established that the fully adaptive optimum can be approximated within factor $2$, which had remained the best-known performance guarantee since then. Their marginal cost accounting and dual-balancing framework made this comparison possible without computing optimal decisions across future trajectories, opening a broad research program on approximation algorithms for stochastic inventory systems. We break this long-standing barrier for periodic-review stochastic inventory control, showing how to compete against the fully adaptive benchmark within factor $\frac{ e }{ e-1 } \approx 1.582$ while retaining general demand correlations and evolving forecasts. We attain these advances by discovering a structural connection between marginal inventory accounting and weighted stopping problems, where each unit's conditional holding charge forms a supermartingale, while postponing its order incurs a history-dependent backlog charge. To leverage the random thresholding approach of Ma and Tzamos (ICML 2023) in this context, we develop a potential-function analysis, leading to an $\frac{ e }{ e-1 }$-approximation with respect to any unit's stopping problem. Subsequently, our common-threshold policy coordinates these marginal decisions into a global replenishment policy without additional loss.

0.20

Optimal Nonparametric Dynamic Pricing with Censored Demand and Adversarial Inventory

cs.LG ·2026-09-26 ·Mengxiao Zhang, Yingfei Wang, Haipeng Luo
benchmarktheory similarity 0.62
Abstract

We study online dynamic pricing with censored demand, where an arbitrary inventory level is revealed before pricing and may adapt to past observations, while demand follows an unknown, price-dependent distribution that is stationary over time. For a horizon of $T$ rounds, Xu et al. [2026] achieved $\widetilde{\mathcal{O}}(\sqrt{T})$ regret under restrictive structural assumptions including linear demand, price-independent additive noise, and conditions relating inventory levels to the noise support. Our first contribution is to extend this framework to a substantially more general and statistically harder nonparametric setting, requiring only the natural assumption that expected sales are nonincreasing in price and allowing nonlinear demand curves and price-dependent noise. For this model, we first propose a simple baseline, Double-Grid-UCB, which discretizes both price and inventory and achieves $\widetilde{\mathcal{O}}(T^{3/4})$ expected regret using separate revenue estimates for each price-inventory grid pair. Then, we develop Threshold-UCB, which improves the expected regret to $\widetilde{\mathcal{O}}(T^{2/3})$. Unlike Double-Grid-UCB, Threshold-UCB reuses sales observations across inventory levels through shared estimates of demand-tail probabilities, allowing the same data to support revenue upper bounds for multiple inventories rather than a single inventory bin. We also complement this upper bound with an $Ω(T^{2/3})$ lower bound via a reduction from stochastic posted pricing, establishing its minimax optimality. Finally, extensive experiments across inventory processes, demand functions, and noise models demonstrate consistently superior performance of Threshold-UCB over benchmark algorithms.

0.23

Resource-Adaptive Primal-Dual Learning for One-Warehouse Multi-Store Systems with Censored Demand

cs.LG math.OC ·2026-08-14 ·Jiameng Lyu
similarity 0.59
Abstract

The one-warehouse multi-store (OWMS) system is a fundamental inventory network in which a nonreplenishable warehouse allocates shared stock across multiple stores over time. Existing OWMS learning policies are built around a fixed target calibrated to the initial average resource rate, but such a fixed-target architecture cannot re-center after realized sales change the remaining resource available per future period. We develop Resource-Adaptive Primal-Dual Learning, a new learning framework that tracks the primal-dual resolving path with censored demand as the remaining-resource state evolves. In each period, the current resource rate indexes the target store allocations and dual variable, while censored sales provide gradient estimates for updating both. The analysis combines expected-sales geometry with a moving-target argument to yield logarithmic expected regret, improving on the state-of-the-art square-root-order guarantees of existing OWMS learning policies. The underlying design and analytical ideas may inform other online learning problems with depleting shared resources. Numerical experiments further demonstrate good finite-horizon performance of a practical variant across different horizon lengths and inventory regimes.

0.04

No-Regret Revenue Maximization in Sequential Market Making Under Inventory Constraints

cs.LG ·2026-10-17 ·Davide Maran, Marcello Restelli, Francesco Emanuele Stradi
theorycode/data similarity 0.59
Abstract

Market makers keep trading efficient by setting bid and ask prices for buyers and sellers. In sequential market making, trades happen independently based on price thresholds, requiring the market maker to maintain balanced, low-risk inventory over T rounds. This paper studies how to maximize revenue with unknown buyer and seller valuations using regret minimization. When the market maker only sees trade success or failure, an algorithm achieves regret and inventory bounds proportional to T to the power of 2/3. When full order book data is available for failed trades, regret and inventory limits improve significantly to the square root of T. We also establish a fundamental trade-off via a lower bound, by proving that tighter round-by-round inventory limits strictly force higher minimum regret.

0.29

An $O(n\log n)$ Algorithm for Uncapacitated Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Arbitrary Prices

cs.CE ·2026-11-17 ·Kleitos Papadopoulos
similarity 0.58
Abstract

We study the finite-horizon, uncapacitated single-item lot-sizing problem with no fixed setup cost, a stationary threshold $Q > 0$ for an all-units quantity discount, arbitrary time-varying regular and discounted unit prices, and nonnegative linear holding costs. Order quantities and inventories may be either continuous or integral, and neither backlogging nor free disposal is allowed. Because unit prices may rise and fall arbitrarily over time, an optimal physical schedule may engage in speculative forward buying: positive orders can occur when incoming stock already exceeds current demand, and physical inventory carried across periods can grow proportionally to total horizon demand rather than remaining bounded by a multiple of $Q$. We give an exact $O(n\log n)$-time algorithm that computes the minimum total cost with free terminal inventory, together with the optimal cost for every horizon prefix constrained to end with zero inventory, using $O(n)$ working space under unit-cost exact arithmetic. Value computation operates online in a single forward pass without lookahead. With persistent frontier snapshots and a linear-time retroactive order-aggregation pass, an optimal physical ordering schedule is recovered in $O(n\log n)$ time and $O(n\log n)$ space.

0.20

Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving

cs.LG math.OC ·2026-09-23 ·Jiameng Lyu
theory similarity 0.58
Abstract

The growth of large language model (LLM) inference and search services increases the scale of online linear programming problems, motivating computationally efficient algorithms. We develop resource-adaptive stochastic gradient descent (RASGD) for stochastic online linear programming. The algorithm uses one request and current inventory to update resource prices, requiring O(m) operations for m resources and memory per arrival and no LP or sample-average optimization. The central idea is to express the current-resource pricing logic of re-solving through a first-order SGD update: each arrival refreshes the remaining-inventory allowance in the dual objective, while the stepsize decreases for early learning and increases later to match the speed of inventory adjustment. Under standard non-degeneracy conditions, our algorithm is feasible on every sample path and achieves O(\log T) expected regret against the realized fractional hindsight optimum, which matches the lower bound, even for policies that know the distribution and have unrestricted computation. The analysis converts curvature around the fixed reference price into inventory stability without tracking optimal prices at changing resource levels. Numerical experiments show that RASGD achieves regret competitive with per-arrival LP re-solving and improves upon the tested first-order baselines, while retaining the computational efficiency of first-order methods. These results establish RASGD as a computationally efficient approach to achieving high allocation quality in large-scale OLP.

0.07