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 s…