Stochastic lot-sizing with backlogging: computational complexity analysis

For a multi-stage stochastic programming problem, one approach is to explore a scenario tree based formulation for the problem and solve the formulation efficiently. There has been significant research progress on how to generate scenario trees in the literature. However, there is limited work on analyzing the computational complexity of the scenario-tree based formulation that considers the number of tree nodes as the input size. In this paper, we use stochastic lot-sizing problems as examples to study the computational complexity issues for the scenario-tree based formulations. We develop production path properties and a general dynamic programming framework based on these properties. The dynamic programming framework allows us to show that the optimal value function is piecewise linear and continuous, which enables us to develop polynomial time algorithms for several different problems, including those with backlogging and varying capacities under certain conditions. As special cases, we develop polynomial time algorithms that run in O(n²){\mathcal{O}(n^2)} and O(n²T log n){\mathcal{O}(n^2T\,{\rm log}\,n)} times, respectively for stochastic uncapacitated and constant capacitated lot-sizing problems with backlogging, regardless of the scenario tree structure.