Reduction from the Partition Problem: Dynamic Lot Sizing Problem with Polynomial Complexity
Chee-Khian Sim · 2024
Read Reduction from the Partition Problem: Dynamic Lot Sizing Problem with Polynomial Complexity by Chee-Khian Sim (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-05017.txt.
Introduction
Chee-Khian Sim links two classic planning puzzles through a shared solution method. His note, from twenty twenty-four, connects the partition problem to dynamic lot sizing. Partition asks whether a set of numbers splits into two equal sums. Lot sizing plans production runs over time to meet demand at least cost.
Sim shows any partition case can be recast as a lot sizing case. Solving the recast case with dynamic programming then answers the partition case. The run time grows in a mild, pseudo-polynomial way. Code tests on sample cases back the claim. He closes by probing whether a fully polynomial route could exist through the same lens.
Catalog record
| CREATOR | Chee-Khian Sim |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-05017
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reduction from the Partition Problem: Dynamic Lot Sizing Problem with Polynomial Complexity Chee-Khian Sim Abstract In this note, we polynomially reduce an instance of the partition problem to a dynamic lot sizing problem, and show that solving the latter problem solves the former problem. By solving the dynamic program formulation of the dynamic lot sizing problem, we show that the instance of the partition problem can be solved with pseudo-polynomial time complexity. Numerical results on solving instances of the partition problem are also provided using an implementation of the algorithm that solves the dynamic program. We conclude by discussing polynomial time solvability of the partition problem through further observation on the dynamic program formulation of the dynamic lot sizing problem. Keywords . Partition problem; dynamic lot sizing model; dynamic program; pseudo-polynomial time complexity; polynomial time complexity. 1 Introduction An NP-complete problem is in the class of NP, and at the same time, it is NP-hard. In this note, we consider solving a well-known NP-complete problem - the partition problem [ 3 , 4 , 5 , 6 ] . We relate the problem to a dynamic lot sizing problem, and by solving the dynamic program formulation of the latter problem, we show that we can solve any instance of the partition problem with pseudo-polynomial time complexity. We conclude this note by discussing the possibility of polynomial time complexity of the partition problem through our approach. Recall from [ 3 ] that an algorithm for a problem is a pseudo-polynomial time algorithm for the problem if for a problem instance I of the problem, its time complexity function is bounded above by a polynomial function of two variables Length [I] and Max [I] , where Length [I] is an integer that corresponds to the number of symbols used to describe I under some reasonable encoding scheme for the problem, while Max [I] is an integer that corresponds to the magnitude of the largest number in I . On the other hand, an algorithm for a problem is a polynomial time algorithm for the problem if for a problem instance I of the problem, its time complexity function is bounded above by a polynomial function of Length [I] . 1.1 Notations Let f(x) and g(x) be two nonnegative real-valued functions, where x\in\mathbb{Z}^{++} . We write g(x)=O(f(x)) to mean that g(x)\leq Kf(x) for some positive constant K and all x>0 . Furthermore, \mathbb{I}(x) , where x\in\mathbb{Z} , is defined to be 1 for x>0 , and 0 otherwise; and x^{+}=\max\{x,0\} , where x\in\Re . Also, we have \min\{x,y\}=x-(x-y)^{+} for x,y\in\Re . 2 The Partition Problem and its Reduction to a Dynamic Lot Sizing Problem Let S=\{1,\ldots,n\} and a_{i}\in\mathbb{Z}^{++} for i\in S , with \sum_{i\in S}a_{i}=2C . The partition problem is to find a subset A of S such that \displaystyle\sum_{i\in A}a_{i}=\sum_{i\in S\backslash A}a_{i}=C. It is known that the partition problem is NP-complete [ 2 , 3 , 4 ] . We call an instance of the partition problem PPi . In this section, we reduce PPi to a dynamic lot sizing problem in polynomial time and show that solving the dynamic lot sizing problem solves PPi in Theorem 2.2 . As a consequence, if the dynamic lot sizing problem can be solved with polynomial complexity in some sense, PPi can also be solved with polynomial complexity in the same sense. Dynamic lot sizing problem is introduced in [ 8 ] , and has since been studied intensively by researchers. We consider a variant of this basic problem which is related to remanufacturing. In the following, we list down the parameters of the dynamic lot sizing model that we are considering in this note: Parameters : • N= number of periods in the time horizon, where N\geq 1 ; • D_{i}= demand for serviceable products in the i^{th} period, where i=1,\ldots,N . We assume that D_{i}\in\mathbb{Z}^{++},i=1,\ldots,N ; • R_{i}= returned products as cores at the beginning of the i^{th} period, where i=1,\ldots,N . We assume that R_{i}\in\mathbb{Z}^{+},i=1,\ldots,N , and set R_{N+1}=0 ; • K_{r,i}= setup cost when there is remanufacturing at the beginning of the i^{th} period, where i=1,\ldots,N . We let K_{r,i}\geq 0 for all i=1,\ldots,N , and set K_{r,N+1}=0 ; • \Delta K_{m,i}= setup cost when there is manufacturing at the beginning of the i^{th} period, where i=1,\ldots,N . We let \Delta K_{m,i}\geq 0 for all i=1,\ldots,N , and set \Delta K_{m,N+1}=0 ; • h_{s,i}= unit holding cost of serviceable product over the i^{th} period whether from manufacturing or remanufacturing, where i=1,\ldots,N . We let h_{s,i}\geq 0 for all i=1,\ldots,N ; • h_{c,i}= unit holding cost of core over the i^{th} period, where i=1,\ldots,N . We let h_{c,i}\geq 0 for all i=1,\ldots,N ; • c_{r,i}= unit remanufacturing cost in the i^{th} period, where i=1,\ldots,N . We let c_{r,i}\geq 0 for all i=2,\ldots,N , and set c_{r,N+1}=0 ; • c_{m,i}= unit manufacturing cost in the i^{th} period, where i=1,\ldots,N . We let c_{m,i}\geq 0 for all i=1,\ldots,N , and set c_{m,N+1}=0 . We further impose assumptions on the above parameters as follows: Assumption 2.1 1. h_{s,i}+c_{m,i}>\Delta K_{m,i+1}+c_{m,i+1} for 1\leq i\leq N ; 2. h_{s,i}+c_{r,i}>K_{r,i+1}+h_{c,i}+c_{r,i+1} for 1\leq i\leq N . These assumptions are crucial to prove Lemma 3.1 , which in turn is needed to formulate the dynamic program for the dynamic lot sizing problem we are considering in this note, and also to solve it efficiently. Demand must be satisfied in each period in our model. Our objective for the model is to minimize its total cost, which comprises of setup costs for manufacturing and remanufacturing, holding costs for serviceable products and cores, manufacturing and remanufacturing costs. We have the following sequence of events in our model - at the beginning of a period, (i) returned products arrive as cores; (ii) number of units of serviceable products to produce through remanufacturing and manufacturing is determined; (iii) demand in the period is satisfied; (iv) any leftover cores and serviceable products are held to the next period. The dynamic lot sizing problem ( DLSP ) we are considering is given by: \displaystyle\min\sum_{i=1}^{N}(K_{r,i}\mathbb{I}(x_{i})+\Delta K_{m,i}\mathbb{I}(y_{i})+c_{r,i}x_{i}+c_{m,i}y_{i}+h_{c,i}[J_{i}-x_{i}]+h_{s,i}I_{i+1}) subject to \displaystyle J_{i+1}=J_{i}+R_{i+1}-x_{i},\ i=1,\ldots,N, \displaystyle I_{i+1}=I_{i}+x_{i}+y_{i}-D_{i},\ i=1,\ldots,N, \displaystyle x_{i}\leq J_{i},\ i=1,\ldots,N, \displaystyle J_{i},I_{i}\geq 0,\ i=2,\ldots,N+1, \displaystyle x_{i},y_{i}\in\mathbb{Z}^{+},\ i=1,\ldots,N, \displaystyle J_{1}=R_{1},I_{1}=0. The decision variables in the above minimization problem are: • x_{i}= number of units of cores remanufactured in the i^{th} period; • y_{i}= number of units of serviceable products obtained by manufacturing in the i^{th} period, while • J_{i}= number of units of cores at the beginning of the i^{th} period; • I_{i}= number of units of available serviceable products at the beginning of the i^{th} period. The objective function in the above minimization problem is the total cost of the model. The first constraint tells us the number of units of cores available at the beginning of the (i+1)^{th} period, i=1,\ldots,N , after events occurred in the i^{th} period. The second constraint tells us the number of units of serviceable products available at the beginning of the (i+1)^{th} period, i=1,\ldots,N , after events occurred in the i^{th} period. The third constraint tells us that the number of cores remanufactured in the i^{th} period cannot exceed the cores available in the period. The fourth constraint tells us that the number of