Publication Type

Working Paper

Version

acceptedVersion

Publication Date

5-2026

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.

Keywords

supply chain management, inventory management, algorithms, computational complexity, linear programming

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Areas of Excellence

Digital transformation

First Page

1

Last Page

69

Publisher

Institute for Operations Research and Management Sciences

Comments

accepted in Management Science

Additional URL

https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5125427

Download

Share

COinS