VI ALIO/EURO Workshop on Applied Combinatorial Optimization


December 15 - 17, 2008, Buenos Aires, Argentina




On solving large-scale planning problems under uncertainty

Laureano F. Escudero

Dpto de Estadistica e Investigacion Operativa

Universidad Rey Juan Carlos, Mostoles (Madrid), Spain

It has long been recognized that traditional deterministic optimization is not suitable for capturing the truly dynamic behavior of most real-life problems, given the uncer- tainty of the parameters that represent information about the future. Many of these problems, planning under uncertainty, have logical constraints that require 01 vari- ables for their formulation. The solution of this type of problems can be performed via Stochastic Integer Programming by using scenario tree analysis. Given the dimensions of the Deterministic Equivalent Model (DEM) of the stochastic problem, some kinds of decomposition approaches can be considered by exploiting the structure of the models. Traditional decomposition schemes, such as Benders and Lagrangean approaches, do not seem to provide the solution for large scale problems (mainly in the cardinality of the scenario tree) in a?ordable computing e?ort. In this work we present a Stochastic Dynamic Programming approach, specially suited for exploiting the structure of the scenario tree and, thus, very amenable for solving very large-scale DEMs.

The Stochastic Dynamic Programming approach that we present utilizes the sce- nario tree in a back-to-front scheme. It obtains the solution of the multi-period stochas- tic problems related to the subtrees whose root nodes are the starting nodes (i.e., sce- nario groups) in each given stage along the time horizon. Each subproblem considers the e?ect 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 us to estimate the EFV curves for the scenario groups from the previous stages, until the curves for the ?rst stage are computed. An application of the scheme to the production planning problem 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 to satisfy the product demand. Some computational experience is reported. The proposed approach compares favorably for very large-scale instances with a state-of-the-art optimization engine.