TY - JOUR

T1 - Integer Factorization

T2 - Why Two-Item Joint Replenishment Is Hard

AU - Schulz, Andreas S.

AU - Telha, Claudio

N1 - Publisher Copyright:
© 2022 INFORMS.

PY - 2024/5/1

Y1 - 2024/5/1

N2 - Distribution networks with periodically repeating events often hold great promise to exploit economies of scale. Joint replenishment problems are fundamental in inventory management, manufacturing, and logistics and capture these effects. However, finding an efficient algorithm that optimally solves these models or showing that none may exist have long been open regardless of whether empty joint orders are possible or not. In either case, we show that finding optimal solutions to joint replenishment instances with just two items is at least as difficult as integer factorization. To the best of the authors’ knowledge, this is the first time integer factorization is used to explain the computational hardness of any optimization problem. We can even prove that the two-item joint replenishment problem with possibly empty joint-ordering points is NP-complete under randomized reductions. This implies that even quantum computers may not be able to solve it efficiently. By relating the computational complexity of joint replenishment to cryptography, prime decomposition, and other aspects of prime numbers, a similar approach may help to establish the (integer-factorization) hardness of additional periodic problems in supply chain management and beyond, whose computational complexity has not been resolved yet.

AB - Distribution networks with periodically repeating events often hold great promise to exploit economies of scale. Joint replenishment problems are fundamental in inventory management, manufacturing, and logistics and capture these effects. However, finding an efficient algorithm that optimally solves these models or showing that none may exist have long been open regardless of whether empty joint orders are possible or not. In either case, we show that finding optimal solutions to joint replenishment instances with just two items is at least as difficult as integer factorization. To the best of the authors’ knowledge, this is the first time integer factorization is used to explain the computational hardness of any optimization problem. We can even prove that the two-item joint replenishment problem with possibly empty joint-ordering points is NP-complete under randomized reductions. This implies that even quantum computers may not be able to solve it efficiently. By relating the computational complexity of joint replenishment to cryptography, prime decomposition, and other aspects of prime numbers, a similar approach may help to establish the (integer-factorization) hardness of additional periodic problems in supply chain management and beyond, whose computational complexity has not been resolved yet.

KW - computational complexity

KW - integer factorization

KW - joint replenishment

UR - http://www.scopus.com/inward/record.url?scp=85195815604&partnerID=8YFLogxK

U2 - 10.1287/opre.2022.2390

DO - 10.1287/opre.2022.2390

M3 - Article

AN - SCOPUS:85195815604

SN - 0030-364X

VL - 72

SP - 1192

EP - 1202

JO - Operations Research

JF - Operations Research

IS - 3

ER -