A unified state-space and scenario tree framework for multi-stage stochastic optimization: An application to emission-constrained hydro-thermal scheduling

In the hydro-thermal scheduling problem, one is interested in determining the optimal operating policy for the use of hydro and thermal resources in order to minimize total expected costs of fulfilling the demand for electricity over a given time horizon. Originally proposed in 1991 by Pereira and Pinto, Stochastic Dual Dynamic Programming (SDDP) remains to date the most efficient algorithm which is able to cope with inflow uncertainty and a detailed representation of a system's characteristics.;In this dissertation, we propose several extensions of the SDDP methodology: We embed the SDDP algorithm into a scenario tree framework, incorporate CO 2 emission allowance constraints, and supplement the profit maximization models to account for CO2 emission allowance markets.;These extensions allows us to additionally deal with uncertainties related to the evolution of demand and fuel prices. From a practical standpoint, this is an innovation as fuel price and electricity demand uncertainty could not be taken into account efficiently in hydro-thermal power systems so far, and from a technical standpoint, this is a new approach unifying the state-space and scenario tree framework.;The importance of such an approach was made evident by the global economic crisis of 2008 when several countries experienced huge variations in demand and faced sudden and sharp increases in fuel costs due to oil price swings, with implications not only on total incurred costs but also regarding security of supply.;Despite the uncertainty surrounding the design of a mechanism which is ultimately accepted by nations worldwide, the necessity to implement measures to curb emissions of greenhouse gases on a global scale is consensual. The electricity sector plays a fundamental role in this puzzle and countries may soon have to revise their operating policy directives in order to make them compatible with additional constraints imposed by such regulations.;Managing an annual emission allowance is somewhat similar to managing water reservoirs since one must determine the optimal trade-off between consuming parts of the limited amount of a resource in the present moment or saving it for future use. The decision to deplete the CO2 stock on hand may only be assessed in terms of its expected future costs, which depend on the evolution of hydrological conditions. Thus, a reservoir model for the CO2 emission quota has been proposed, respecting the stage decomposition framework of stochastic dynamic programming methods. This reservoir model allows for CO2 allowances to expire at given times. This is practically of high importance as this model reflects the currently implemented policy of the EU Emission Trading Scheme.;The deregulation of the electricity markets made it necessary to incorporate uncertain electricity prices into the optimization models. Those models are typically solved using a hybrid method of the stochastic dynamic programming and stochastic dual dynamic programming. We extend those methods by incorporating stochastic CO2 emission allowance prices and stochastic fuel prices. The input data are derived by a fundamental model which allows us to capture the joint correlation of electricity market prices, CO2 emission allowance prices, fuel prices and hydro inflows.