From Trees to Treewidth: Inventory Management in Complex Supply Chain Networks

Abstract

We propose an exact solution approach to the Guaranteed Service Model (GSM), one of the most widely applied models for optimizing safety stock placement in supply chain networks. Based on linear programming (LP), our approach handles any directed acyclic network and any cost function that depends on a stage's incoming and outgoing service times. It scales polynomially in the number of nodes n in the network, and exponentially in its treewidth, which quantifies how "tree-like" a network is, and can be much smaller than n. This contrasts with existing approaches, which scale exponentially in n. The proof of exactness of our approach relies crucially on showing that the join of transportation-like polytopes remains integral, and it is more broadly applicable to other Operations Management problems. The use of linear programming makes for straightforward implementation, including when incorporating additional operational constraints. It also enables sensitivity analyses and the construction of principled bounds on the GSM's optimal value. Finally, it allows for the use of standard LP optimization software, resulting in considerable gains in solving time. In particular, we demonstrate that, on real-world data from Willems (2008), we achieve consistent and significant optimization speed-ups compared to the state-of-the-art approach for the GSM and commercial all-purpose solvers. Overall, our approach builds a new bridge between operations Management and Computer Science, thereby providing new theoretical foundations and practical tools for managing safety stocks in complex modern supply chain networks.