M.P. Nowak, W. Römisch
Stochastic Lagrangian Relaxation applied to Power Scheduling in a Hydro-Thermal System under Uncertainty
Preprint series: Institut fuer Mathematik, Humboldt-Universität zu Berlin (ISSN 0863-0976)

MSC:

90C15 Stochastic programming

90C11 Mixed integer programming

90B30 Production models

Abstract: A dynamic (multi-stage) stochastic programming model for the weekly
cost-optimal generation of electric power in a hydro-thermal generation
system under uncertain load is developed. The model involves a large number
of mixed-integer (stochastic) decision variables and constraints linking
time periods and operating power units. A stochastic Lagrangian relaxation
scheme is designed by assigning (stochastic) multipliers to all constraints
coupling power units. It is assumed that the stochastic load process is
given (or approximated) by a finite number of realizations (scenarios) in
scenario tree form. Solving the dual by a bundle subgradient method
leads to a successive decomposition into stochastic single (thermal or hydro)
unit subproblems. The stochastic thermal and hydro subproblems are solved by
a stochastic dynamic programming technique and by a specific descent
algorithm, respectively. A Lagrangian heuristics that provides approximate
solutions for the first stage (primal) decisions starting from the optimal
(stochastic) multipliers is developed. Numerical results are presented for
realistic data from a German power utility and for numbers of scenarios
ranging from 5 to 100 and a time horizon from 7 to 9 days. The sizes of the
corresponding optimization problems go up to 200.000 binary and 350.000
continuous variables, and more than 500.000 constraints.
Keywords: Multi-stage stochastic program, mixed-integer, stochastic Lagrangian relaxation, power generation, hydro-thermal system, uncertain load