Combining Polyhedral Approaches and Stochastic Dual Dynamic Integer Programming for Solving the Uncapacitated Lot-Sizing Problem under Uncertainty

We study the uncapacitated lot-sizing problem with uncertain demand and costs. The problemismodeled as amultistage stochasticmixed-integer linear programinwhich the evolution of the uncertain parameters is represented by a scenario tree. To solve this problem, we propose a new extension of the stochastic dual dynamic integer programming algorithm (SDDiP). This extension aims at being more computationally efficient in the management of the expected cost-to-go functions involved in the model, in particular by reducing their number and by exploiting the current knowledge on the polyhedral structure of the stochastic uncapacitated lot-sizing problem. The algorithm is based on a partial decomposition of the problem into a set of stochastic subproblems, each one involving a subset of nodes forming a subtree of the initial scenario tree. We then introduce a cutting plane-generation procedure that iteratively strengthens the linear relaxation of these subproblems and enables the generation of an additional strengthened Benders' cut,which improves the convergence of themethod. We carry out extensive computational experiments on randomly generated large-size instances. Our numerical results show that the proposed algorithm significantly outperforms the SDDiP algorithmat providing good-quality solutionswithin the computation time limit. Summary of Contribution: This paper investigates a combinatorial optimization problem called the uncapacitated lot-sizing problem. This problemhas beenwidely studied in the operations research literature as it appears as a core subprobleminmany industrial production planning problems. We consider a stochastic extension in which the input parameters are subject to uncertainty and model the resulting stochastic optimization problem as a multistage stochastic integer program. To solve this stochastic problem,we propose a novel extension of the recently published stochastic dual dynamic integer programming (SDDiP) algorithm. The proposed extension relies on two main ideas: the use of a partial decomposition of the scenario tree and the exploitation of existing knowledge on the polyhedral structure of the stochastic uncapacitated lot-sizing problem. We provide the results of extensive computational experiments carried out on large-size randomly generated instances. These results show that the proposed extended algorithm significantly outperforms the SDDiP at providing good-quality solutions for the stochastic uncapacitated lot-sizing problem. Although the paper focuses on a basic lot-sizing problem, the proposed algorithmic framework may be useful to solvemore complex practical production planning problems.