Multistage Stochastic Programming: A Scenario Tree Based Approach to Planning under Uncertainty

Multistage Stochastic Programming: A Scenario Tree Based Approach to Planning under Uncertainty

Boris Defourny (University of Liège, Belgium), Damien Ernst (University of Liège, Belgium) and Louis Wehenkel (University of Liège, Belgium)
DOI: 10.4018/978-1-60960-165-2.ch006
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

In this chapter, we present the multistage stochastic programming framework for sequential decision making under uncertainty. We discuss its differences with Markov Decision Processes, from the point of view of decision models and solution algorithms. We describe the standard technique for solving approximately multistage stochastic problems, based on a discretization of the disturbance space called scenario tree. We insist on a critical issue of the approach; the decisions can be very sensitive to the parameters of the scenario tree, whereas no efficient tool for checking the quality of approximate solutions exists. In this chapter, we show how supervised learning techniques can be used to evaluate reliably the quality of an approximation, and thus facilitate the selection of a good scenario tree. The framework and solution techniques presented in the chapter are explained and detailed on several examples. Along the way, we define notions from decision theory that can be used to quantify, for a particular problem, the advantage of switching to a more sophisticated decision model.
Chapter Preview
Top

Background

Now, even if we insist on concepts, our presentation cannot totally escape from the fact that multistage stochastic programming uses optimization techniques from mathematical programming, and can harness advances in the field of optimization.

Complete Chapter List

Search this Book:
Reset