Base-Stock Policies are Close to Optimal for Newsvendor Networks

We provide the first approximation algorithm for dynamic newsvendor networks with stochastic demand and backlogging. Specifically, under a mild cost condition we prove the cost of a base-stock policy is less than 1.618 times the cost of an optimal policy. This answers an open question of Van Mieghem and Rudi (2002) on the effectiveness of base-stock policies in general newsvendor networks with backlogging. To prove our result, we innovate solutions to two main technical challenges. First, we define a new class of base-stock policies that address the currently unresolved issue of how to assign and fulfill backlogs in a system with fulfillment flexibility. We then characterize the optimal policy in this class via the solution of a two stage stochastic program. Second, we prove that this class of base-stock policies performs well relative to an optimal policy, despite the fact that the structure of optimal policies in such a general setting is either unknown or exceedingly complex. To do so, we construct a novel lower bound on optimal cost via the solution of a second stochastic program, which we use to bound the cost of the first stochastic program. We also demonstrate our policy's practicality with numerical simulations that show it performs within 1% of optimal on average. Finally, we show that our techniques and results extend to more general settings, demonstrating their potential for broader applicability. Importantly, our approach extends to problems with lead times, where we prove an approximation guarantee for base-stock policies that is independent of both the lead time and network structure