Constant Depth Decision Rules for Multistage Stochastic Convex Programs

Abstract

In this paper, we introduce a new class of decision rules called Constant Depth Decision Rules (CDDRs) for Multistage Stochastic Convex Programs (MSCP) depending on a parame- ter Mi called the depth of the decision rules. More precisely, the decision for stage t is expressed as the sum of t functions of Mi consecutive values of the underlying stochastic process. We con- sider two classes of stochastic processes: processes with discrete known distributions and processes with unknown distributions whose support is a known polyhedral set. For these two classes, we show how to reformulate the corresponding approximate problem as a linear (resp. nonlinear and of the same structure) program when the original MSCP is linear (resp. nonlinear) where the number of variables and constraints is polynomial in some variable expressed in terms of Mi and the problem parameters. We also describe the functions of a library available on Github at https://github.com/vguigues/Constant_Depth_Decision_Rules_Library, implementing CD- DRs for multistage stochastic linear programs. Finally, we present the results of encouraging numerical results on a hydro-thermal planning problem with interstage dependent in ows where CDDRs are computed much quicker than Stochastic Dual Dynamic Programming policy and pro- vide very similar average costs as long as the number of stages and number of realizations of in ows per stage are not too large and Mi is not too small.