Decomposition of dynamic single-product and multi-product lotsizing problems and scalability of EDAs

In existing theoretical and experimental work, Estimation of Distribution Algorithms (EDAs) are primarily applied to decomposable test problems. State-of-the-art EDAs like the Hierarchical Bayesian Optimization Algorithm (hBOA), the Learning Factorized Distribution Algorithm (LFDA) or Estimation of Bayesian Networks Algorithm (EBNA) solve these problems in polynomial time. Regarding this success, it is tempting to apply EDAs to real-world problems. But up to now, it has rarely been analyzed which real-world problems are decomposable. The main contribution of this chapter is twofold: (1) It shows that uncapacitated single-product and multi-product lotsizing problems are decomposable. (2) A state-of-the-art EDA is used to solve both problems. The problems are fundamental in inventory management and their fitness functions can be expressed as additively decomposable functions. It is analyzed how a search distribution of Boltzmann-type factorizes for these functions and it is shown that the factorizations of the Boltzmann distribution are polynomially bounded. Consequently, experimental scalability analysis is conducted for both problems with a state-of-the-art EDA. The total number of fitness evaluations required to reliably solve the problems to optimality is found to grow with a low-order polynomial depending on the problem size. The results confirm existing scalability theory for decomposable problems.