 |
Center for Nonlinear Studies |
Multi-stage stochastic optimization can be used to model dynamic decision-making environments in which a sequence of decisions are to be made in response to a sequence of random events. Such problems arise in many applications, such as unit commitment and economic dispatch in power systems and inventory and production management. Many approaches for solving multi-stage stochastic optimization problems rely on a given scenario-tree approximation of the underlying stochastic process. Unfortunately, the size of the scenario tree required to approximate a stochastic process in general grows exponentially with the number of decision stages, making this approach limited in practice to problems with few stages. We present a new approximate solution approach that eliminates the reliance on scenario trees. Our approach is based on considering a Lagrangian relaxation of the multi-stage stochastic program, and restricting the Lagrangian dual variables to follow a linear decision rule. The resulting approximation problem has the form of a two-stage stochastic program which can be approximately solved via sampling and decomposition algorithms. Because it is based on a relaxation, the approximation provides a lower bound on the optimal value. We consider application of this approach for two different restricted Lagrangian duals and compare the resulting bound quality. We also demonstrate how the optimal solution of the relaxation can be used to drive a primal policy. A numerical illustration on a multi-item stochastic lot sizing problem is provided that demonstrates the potential for the approach to yield bounds and policies that improve upon existing approaches.
Host: Russell Bent