Integer Factorization: Why Two-Item Joint Replenishment Is Hard

• Published in: Operations research 2024-05, Vol.72 (3), p.1192-1202
• Main Authors: Schulz, Andreas S., Telha, Claudio
• Format: Article
• Language: English
• Subjects: Algorithms; Complexity; computational complexity; Distribution management; Economies of scale; Factorization; Hardness; integer factorization; Integers; Inventory management; joint replenishment; Mathematical problems; Optimization; Prime numbers; Quantum computers; Replenishment; Supply chain management; Supply chains; Surface hardness
• ISSN: 0030-364X; 1526-5463
• DOI: 10.1287/opre.2022.2390

Joint replenishment problems constitute an important class of models in inventory management. They exhibit aspects of possible coordination among multiple products to save costs. Their computational complexity had been open even if there are just two products that need to be synced. In “Integer factorization: Why two-item joint replenishment is hard,” Schulz and Telha present a simple framework based on integer factorization to establish the computational hardness of two variants of the joint replenishment problem with two items. Whereas difficult to solve in practice and not believed to be solvable in polynomial time, integer factorization is not as difficult as NP-complete problems. The authors show that a similar technique can be used to show even the NP-completeness of one variant of the joint replenishment problem (again with just two items). 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. Funding: The first author gratefully acknowledges the support of the Alexander von Humboldt Foundation and the German Federal Ministry of Education and Research. The second author gratefully acknowledges the support of Agencia Nacional de Investigación y Desarrollo [Grant ANID/FONDECYT Iniciación 11200616] and Progra