Skip to main content
SpringerLink
Log in

Stochastic Lagrangian Relaxation Applied to Power Scheduling in a Hydro-Thermal System under Uncertainty

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

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 demand (or 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 of 168 hours. The sizes of the corresponding optimization problems go up to 200 000 binary and 350 000 continuous variables, and more than 500 000 constraints.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. D.P. Bertsekas, G.S. Lauer, N.R. Sandell Jr. and T.A. Posbergh, Optimal short-term scheduling of large-scale power systems, IEEE Transactions on Automatic Control AC-28 (1983) 1–11.

    Google Scholar 

  2. J.R. Birge, Stochastic programming computations and applications, INFORMS Journal on Computing 9(1997) 111–133.

    Google Scholar 

  3. J.R. Birge and F. Louveaux, Introduction to Stochastic Programming(Springer, New York, 1997).

    Google Scholar 

  4. P.P.J. van den Bosch, Optimal static dispatch with linear, quadratic and nonlinear functions of the fuel costs, IEEE Transactions on Power Apparatus and Systems PAS-104 (1985) 3402–3408.

  5. P.P.J. van den Bosch and F.A. Lootsma, Scheduling of power generation via large-scale nonlinear optimization, Journal of Optimization and Applications 55(1987) 1684–1690.

    Google Scholar 

  6. C.C. Carøe and R. Schultz, Dual decomposition in stochastic integer programming, Operations Re-search Letters 24(1999) 37–45.

    Google Scholar 

  7. C.C. Carøe and R. Schultz, A two-stage stochastic program for unit commitment under uncertainty in a hydro-thermal power system, DFG-Schwerpunktprogramm Echtzeit-Optimierung großer Systeme, Preprint 98–13 (1998).

  8. P. Carpentier, G. Cohen, J.-C. Culioli and A. Renaud, Stochastic optimization of unit commitment: a new decomposition framework, IEEE Transactions on Power Systems 11(1996) 1067–1073.

    Google Scholar 

  9. D. Dentcheva, R. Gollmer, A. Möller, W. Römisch and R. Schultz, Solving the unit commitment problem in power generation by primal and dual methods, in: Progress in Industrial Mathematics at ECMI 96, eds. M. Brøns, M.P. Bendsøe and M.P. Sørensen (Teubner, Stuttgart, 1997) pp. 332–339.

  10. D. Dentcheva and W. Römisch, Optimal power generation under uncertainty via stochastic program-ming, in: Stochastic Programming Methods and Technical Applications, eds.K. Marti and P. Kall, Lecture Notes in Economics and Mathematical Systems, Vol. 458 (Springer, Berlin, 1998) pp. 22–56.

    Google Scholar 

  11. S. Feltenmark and K.C. Kiwiel, Dual applications of proximal bundle methods, including Lagrangian relaxation of nonconvex problems, SIAM Journal on Optimization 10(2000) 697–721.

    Google Scholar 

  12. S.-E. Fleten, S.W. Wallace and W.T. Ziemba, Portfolio management in a deregulated hydropower based electricity market, in: Hydropower '97,eds. E.Broch, D.K. Lysne, N.Flatabøand E.Helland-Hansen (Balkema, Rotterdam, 1997).

  13. A. Gjelsvik, T.A. Røtting and J. Røynstrand, Long-term scheduling of hydro-thermal power systems, in: Hydropower '92, eds. E. Broch and D.K. Lysne (Balkema, Rotterdam, 1992) pp. 539–546.

  14. R. Gollmer, A. Möller, W. Römisch, R. Schultz, G. Schwarzbach and J. Thomas, Optimale Block-auswahl bei der Kraftwerkseinsatzplanung der VEAG, in: Optimierung in der Energieversorgung II, VDI-Berichte, Vol. 1352 (Düsseldorf, 1997) pp. 71–85.

  15. N. Gröwe, W. Römisch, R. Schultz, A simple recourse model for power dispatch under uncertain demand, Annals of Operations Research 59(1995) 135–164.

    Google Scholar 

  16. J.L. Higle and S. Sen, Stochastic Decomposition—A Statistical Method for Large Scale Stochastic Linear Programming(Kluwer, Dordrecht, 1996).

    Google Scholar 

  17. G. Infanger, Planning Under Uncertainty—Solving Large-Scale Stochastic Linear Programs(Boyd and Fraser, 1994).

  18. J. Jacobs, G. Freeman, J. Grygier, D. Morton, G. Schultz, K. Staschus and J. Stedinger, SOCRATES: A system for scheduling hydroelectric generation under uncertainty, Annals of Operations Research 59(1995) 99–133.

    Google Scholar 

  19. K.C. Kiwiel, Proximity control in bundle methods for convex nondifferentiable optimization, Mathe-matical Programming 46(1990) 105–122.

    Google Scholar 

  20. K.C. Kiwiel, User's Guide for NOA 2.0/3.0: A Fortran package for convex nondifferentiable opti-mization, Polish Academy of Sciences, Systems Research Institute, Warsaw, Poland (1993/94).

    Google Scholar 

  21. K.C. Kiwiel, Approximations in proximal bundle methods and decomposition of convex programs, Journal of Optimization Theory and Applications 84(1995) 529–548.

    Google Scholar 

  22. P. Kleinmann and R. Schultz, A simple procedure for optimal load dispatch using parametric pro-gramming, ZOR—Methods and Models of Operations Research 34(1990) 219–229.

    Google Scholar 

  23. C. Lemaréchal, Lagrangian decomposition and nonsmooth optimization, in: Nonsmooth Optimization Methods and Applications, ed. F. Gianessi (Gordon and Breach, 1992) pp. 201–216.

  24. C. Lemaréchal and A. Renaud, A geometric study of duality gaps, with applications, Mathematical Programming (to appear).

  25. A. Løkketangen and D.L. Woodruff, Progressive hedging and tabu search applied to mixed integer (0,1) multi-stage stochastic programming, Journal of Heuristics 2(1996) 111–128.

    Google Scholar 

  26. V.I. Norkin, G. Pflug and A. Ruszczyński, A branch and bound method for stochastic global optimiza-tion, Mathematical Programming 83(1998) 425–450.

    Google Scholar 

  27. M.P. Nowak, A fast descent method for the hydro storage subproblem in power generation, Interna-tional Institute for Applied Systems Analysis, Laxenburg, Austria, Working Paper WP–96–109 (1996).

  28. M.P. Nowak and W. Römisch, Optimal power dispatch via multistage stochastic programming, in: Progress in Industrial Mathematics at ECMI 96, eds. M. Brøns, M.P. Bendsøe and M.P. Sørensen (Teubner, Stuttgart, 1997) pp. 324–331.

  29. M.V.F. Pereira and L.M.V.G. Pinto, Multi-stage stochastic optimization applied to energy planning, Mathematical Programming 52(1991) 359–375.

    Google Scholar 

  30. A. Renaud, Optimizing short-term operation of power generation: a new stochastic model, Lecture presented at the VIII International Conference on Stochastic Programming, Vancouver, Canada (Au-gust 1998).

  31. R.T. Rockafellar and R.J.-B. Wets, The optimal recourse problem in discrete time: L1-multipliers for inequality constraints, SIAM Journal on Control and Optimization 16(1978) 16–36.

    Google Scholar 

  32. R.T. Rockafellar and R.J.-B. Wets, Scenarios and policy aggregation in optimization under uncer-tainty, Mathematics of Operations Research 16(1991) 119–147.

    Google Scholar 

  33. W. Römisch and R. Schultz, Decomposition of a multi-stage stochastic program for power dispatch, ZAMM—Zeitschrift für Angewandte Mathematik und Mechanik 76(Suppl. 3) (1996) 29–32.

    Google Scholar 

  34. A. Ruszczyński, Decomposition methods in stochastic programming, Mathematical Programming, Series B 79 (1997) 333–353.

  35. G.B. Sheble and G.N. Fahd, Unit commitment literature synopsis, IEEE Transactions on Power Sys-tems 9(1994) 128–135.

    Google Scholar 

  36. S. Takriti, J.R. Birge and E. Long, A stochastic model for the unit commitment problem, IEEE Trans-actions on Power Systems 11(1996) 1497–1508.

    Google Scholar 

  37. S. Takriti, B. Krasenbrink and L.S.-Y. Wu, Incorporating fuel constraints and electricity spot prices into the stochastic unit commitment problem, Operations Research 48(2000) 268–280.

    Google Scholar 

  38. R.J.-B. Wets, Stochastic Programming, in: Handbooks in Operations Research and Management Science,Vol.1,Optimization, eds. G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd (North-Holland, Amsterdam, 1989) pp. 573–629.

    Google Scholar 

  39. A.J. Wood and B.F. Wollenberg, Power Generation, Operation, and Control, 2nd edn. (Wiley, New York, 1996).

    Google Scholar 

  40. F. Zhuang and F.D. Galiana, Towards a more rigorous and practical unit commitment by Lagrangian relaxation, IEEE Transactions on Power Systems 3(1988) 763–773.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics, Humboldt University Berlin, 10099, Berlin, Germany

    Matthias P. Nowak

  2. Institute of Mathematics, Humboldt University Berlin, 10099, Berlin, Germany

    Werner Römisch

Authors
  1. Matthias P. Nowak
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Werner Römisch
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Nowak, M.P., Römisch, W. Stochastic Lagrangian Relaxation Applied to Power Scheduling in a Hydro-Thermal System under Uncertainty. Annals of Operations Research 100, 251–272 (2000). https://doi.org/10.1023/A:1019248506301

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1019248506301

Search

Navigation