Cost Balancing for Sparse Newsvendor Networks

We study newsvendor network (NN) models for managing inventory in multi-resource, multi-product systems that involve both common resource requirements and fulfillment flexibility. Such systems arise in a wide range of applications, including production and e-commerce, but optimizing their performance is a challenging problem due to a combinatorial resource allocation decision. We provide new insight for NN problems by identifying network sparsity as key for efficient optimization: a wide range of sparse networks can be solved approximately, while networks without sparsity can be NP-hard, even to approximate. We derive these insights by developing a novel framework for balancing inventory costs (or "overage") and shortage costs (or "underage") in NN problems. Intuitively, there is an inherent trade-off between inventory and shortage costs, but the multi-dimensional nature of the NN problem makes exploiting this trade-off challenging. Our approach, called newsvendor cost balancing (NCB), uses LP rounding to develop bounds characterizing this trade-off in a low-dimensional parameter space, and then balances the costs to obtain a good solution and performance guarantee. This approach provides good approximation guarantees if the network is sparse with respect to any of the following: i) fulfillment flexibility, ii) resource requirements, or iii) activity usage. This is beneficial practically, as we demonstrate that many realistic production and e-commerce networks exhibit these types of sparsity, and in numerical simulations on such networks our algorithm comes within 3% of optimal on average. Finally, when applied to the special case of the ATO problem, our approach improves the best known constant factor approximation to 1.582