Publication Type

Journal Article

Version

publishedVersion

Publication Date

9-2026

Abstract

We propose an exact linear programming (LP)-based solution approach to the Guaranteed Service Model (GSM), one of the most widely applied models for optimizing safety stock placement in supply chain networks. 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, pseudo-polynomially with respect to the bit size of the maximum replenishment time M, and (for fixed M) 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 relies crucially on showing that the join of transportation-like polytopes remains integral and is more broadly applicable to other Operations Management problems. In addition to an exact formulation, our LP-based approach enables a practical solution strategy for the GSM built on a hierarchy of LP relaxations. These relaxations provide valid lower bounds, certify optimality when integral, and can strengthen existing exact methods. In our computational study, the smallest relaxation already recovers an optimal GSM solution on every real-world benchmark instance, leading to substantial speed-ups over the state-of-the-art exact algorithm and commercial general-purpose solvers. The framework also supports sensitivity analysis and accommodates additional operational constraints. Overall, our approach builds a new bridge between Operations Management and Computer Science, 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

Publication

Management Science

First Page

1

Last Page

18

ISSN

0025-1909

Identifier

10.1287/mnsc.2025.03155

Publisher

Institute for Operations Research and Management Sciences

Additional URL

https://doi.org/10.1287/mnsc.2025.03155

Download

Share

COinS