New Approximate Solution Approaches for Multi-Stage Stochastic Optimization

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 adequately represent the evolution of 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 new approximate solution approaches for multi-stage stochastic linear and integer problems in settings where the number of stages is large, so that the scenario-tree approach is intractable. In addition to providing a decision policy, these approaches also yield bounds on the objective value of an optimal policy.

This is joint work with Merve Bodur at the University of Toronto.