A branch and bound algorithm for a single item nonconvex dynamic lot sizing problem with capacity constraints (Q583078)

The following model of a single item \(T\)-period lot sizing problem is considered: Minimize \(f(x,I)\) subject to \((x,I)\in G\cap C\), where \((x,I)=(x_1, \dots, x_ T,I_1, \dots,I_ T) \in R^{2T}\), \(f(x,I)=\sum^{T}_{i=1}f_ i(x_ i) + \sum^{T}_{i=1}h_ i I_ i\), \(G =\{(x,I)\in R^{2T}: x_ i + I_{i-1} - I_ i = d_ i\), \(i=1, \dots, T\), \(I_ 0=0\}\), \(C=\{(x,I)\in R^{2T}: 0\leq x_ i\leq u_ i\), \(0\leq I_ i\leq S_ i\), \(i=1, \dots, T\}.\) The cost function \(f_ i(x_ i)\) for period \(i\), \(i=1, \dots, T\), is of the fo rm \[ f_ i(x_ i) = \begin{cases} 0 & \text{if } x_ i = 0, \\ F_ i + c_ i x_ i & \text{if } 0<x_ i\leq r_ i, \\ F_ i + r_ i c_ i + o_ i(x_ i -r_ i) & \text{if } r_ i < x_ i \leq u_ i. \end{cases} \] So, it is neither convex nor concave. It is a composite function with a fixed setup cost to start the production and a piecewise linear and convex variable production cost. The authors present a branch and bound algorithm which finds a global optimum solution for the problem after solving a finite number of linear knapsack problems with bounded variables. The results of computational experiments performed on the algorithm, which have been presented in the paper, suggest that it is computationally efficient both in terms of CPU time and storage requirements.