On Stochastic Dynamic Programming for solving large-scale

Laburpena

We present a stochastic dynamic programming approach for solving largescale multistage mixed 0�1 programs with uncertainty in some parameters. The proposed scheme utilizes the scenario tree from back-to-front and obtains the solution of the multi-period stochastic problems related to the subtrees whose root nodes are the starting nodes (i.e., scenario groups) in each given stage along the time horizon. Each subproblem considers the effect of the stochasticity of the uncertain parameters from the periods of the given stage, by using curves that estimate the expected future value (EFV) of the objective function. Each subproblem is solved for a set of reference levels of the variables that also have nonzero elements in any of the previous stages besides the given stage. An appropriate sensitivity analysis of the objective function for each reference level of the linking variables allows to estimate the EFV curves for the scenario groups from the previous stages, until the curves for the first stage are computed. An application of the scheme to the tactical production planning with logical constraints is presented. The aim of the problem consists of obtaining the tactical production planning over the scenarios along the time horizon. The expected total cost is minimized for satisfying the product demand. Some computational experience is reported. The proposed approach compares favorably with a state-of-the-art optimization engine.