A 1.79-approximation algorithm for a continuous review lost-sales inventory model

Oct 11 2019 - 1pm to Oct 11 2019 - 2pm


Linwei Xin




Single-sourcing lost-sales inventory systems with lead times are notoriously difficult to optimize. Recent numerical experiments have suggested that a so-called capped base-stock policy demonstrates superior performance compared with existing heuristics. However, the superior performance lacks of a theoretical foundation and why such a policy performs so well in general remains a major open question. In this paper, we provide a theoretical foundation for this phenomenon. In a continuous review lost-sales inventory model with lead times and Poisson demand, we prove that this policy has a worst-case performance guarantee of 1.79 by conducting an asymptotic analysis under large penalty cost and lead time following Reiman (2004). This result provides a deeper understanding of the superior numerical performance of capped base-stock policies, and lays the foundations for a new approach to proving worst-case performance guarantees of simple policies in notoriously hard inventory problems. As a by-product of the paper, we also derive a sufficient condition for a base-stock policy to be optimal.



Linwei Xin is an assistant professor of Operations Management at the University of Chicago Booth School of Business. His research interests include supply chain, inventory and revenue management, optimization under uncertainty, and data-driven decision-making. His work has been recognized with several paper competition awards, including the 2017 CSAMSE Best Paper Award, First Place in the 2015 George E. Nicholson Student Paper Competition, Second Place in the 2015 JFIG Paper Competition, and a finalist in the 2014 MSOM Student Paper Competition.