Interior-Point Method for Reservoir Operation with Stochastic Inflows
Publication: Journal of Water Resources Planning and Management
Volume 127, Issue 1
Abstract
A new method is proposed for long-term reservoir operation planning with stochastic inflows. In particular, the problem is formulated as a two-stage stochastic linear program with simple recourse. The stochastic inflows are approximated by multiple inflow scenarios, leading to a very large deterministic model which is hard to solve using conventional optimization methods. This paper presents an efficient interior-point optimization algorithm for solving the resulting deterministic problem. It is also shown how exploiting the problem structure enhances the performance of the algorithm. Application to regulation of the Great Lakes system shows that the proposed approach can handle the stochasticity of the inflows as well as the nonlinearity of the operating conditions in a real-world reservoir system.
Get full access to this article
View all available purchase options and get full access to this article.
References
1.
Birge, J. R., Dempster, M. A. H., Gassmann, H. I., Gunn, E. A., King, A. J., and Wallace, S. W. ( 1987). “A standard input format for multi-period stochastic linear programs.” Comm. on Algorithms Newsletter of Math. Programming Soc., 17, 1–19.
2.
Birge, J. R., Donohue, C. J., Holmes, D. F., and Svintsitski, O. G. ( 1996). “A parallel implementation of the nested decomposition algorithm for multistage linear programs.” Math. Programming, 75, 327–352.
3.
Birge, J. R., and Holmes, D. F. ( 1992). “Efficient solution of two-stage stochastic linear programs using interior-point methods.” Computational Optimization and Applications, 1, 245–276.
4.
Czyzyk, J., Fourer, R., and Mehrotra, S. ( 1995). “A study of the Augmented system and column-splitting approaches for solving two-stage stochastic linear programs by interior-point methods.” ORSA J. on Computing, 474–490.
5.
Dantzig, G., and Glynn, P. W. ( 1989). A workshop on resource planning under uncertainty for electric power systems, Dept. of Operations Research, Stanford Univ., Stanford, Calif.
6.
Dembo, R. S. ( 1991). “Scenario optimization.” Ann. of Operations Res., 30, 63–80.
7.
Dupaová, J. ( 1979). “Water resources system modelling using stochastic programming with recourse.” Recent results in stochastic programming, P. Kall and A. Prékopa, eds., Springer, New York, 121–134.
8.
Dupaová, J. ( 1996). “Scenario-based stochastic programs: Resistance with respect to sample.” Ann. of Operations Res., 64, 21–38.
9.
Environment Canada. ( 1991). Great Lakes levels regulation, draft report, Sysnet model, Ottawa.
10.
Environment Canada. ( 1992). Great Lakes data summary, draft report, Ottawa.
11.
Fletcher, S., and Ponnambalam, K. ( 1998). “A constrained state formulation for the stochastic control of multireservoir systems.” Water Res. Res., 34(2), 257–270.
12.
Hipel, K. W., and McLeod, A. I. ( 1994). Time series modelling of water resources and environmental systems, Elsevier, Amsterdam.
13.
International Joint Committee. ( 1993). Great Lakes levels reference study, annex 3, final report, Windsor, Ontario, Canada.
14.
Jacobs, J., et al. ( 1995). “Stochastic optimal coordination of river-basin and thermal electric systems (SOCRATES): A system for scheduling hydroelectric generation under uncertainty.” Ann. of Operations Res., 59, 99–133.
15.
Karmarkar, N. ( 1984). “A polynomial time algorithm for linear programming.” Combinatorica, 4, 373–395.
16.
Loucks, D. P., Stedinger, J. R., and Haith, D. A. ( 1981). Water resource systems planning and analysis, Prentice-Hall, Englewood Cliffs, N.J.
17.
Lustig, I. J., Mulvey, J., and Carpenter, T. ( 1991). “Formulating stochastic programs for interior-point methods.” Operations Res., 39(5), 757–770.
18.
Mehrotra, S. ( 1992). “On the implementation of a primal-dual interior point method.” SIAM J. on Optimization, 2, 575–601.
19.
Morton, D. P. ( 1996). “An enhanced decomposition algorithm for multistage stochastic hydroelectric scheduling.” Ann. of Operations Res., 64, 211–235.
20.
Mulvey, J. M., and Vladimirou, H. ( 1991). “Applying the progressive hedging algorithm to stochastic generalized networks.” Ann. of Operations Res., 31, 399–424.
21.
Palacios-Gomez, F., Lasdon, L., and Engquist, M. ( 1982). “Nonlinear optimization by successive linear programming.” Mgmt. Sci., 2(10), 1106–1120.
22.
Pereira, M. V. F., and Pinto, L. M. V. G. ( 1991). “Multi-stage stochastic optimization applied to energy planning.” Math. Programming, 52, 359–375.
23.
Ponnambalam, K., and Adams, B. J. ( 1996). “Stochastic optimization of multireservoir systems using a heuristic algorithm: A case study from India.” Water Resour. Res., 32(3), 733–741.
24.
Ponnambalam, K., Vannelli, A., and Unny, T. E. ( 1989). “An application of Karmarkar's interior-point linear programming algorithm for multi-reservoir operations optimization.” Stochastic Hydro. and Hydr., 3, 17–29.
25.
Reznicek, K. K., and Cheng, T. C. E. ( 1991). “Stochastic modelling of reservoir operations.” Eur. J. Operational Res., 50, 235–248.
26.
Seifi, A., and Tunçel, L. ( 1998). “A constant-potential infeasible-start interior-point algorithm with computational experiments and applications.” J. Computational Optimization and Applications, 9(2), 107–152.
27.
Seifi, A., Tunçel, L., and Hipel, K. W. ( 1994). “An improved interior-point approach for use in reservoir operation.” Advances in water resources technology and management, G. Tsakiris and M. A. Santos, eds., Balkema, Rotterdam, The Netherlands, 213–220.
28.
Srinivasan, R., and Simonovic, S. ( 1994). “A reliability programming model for hydropower optimization.” Can. J. Civ. Engrg., Ottawa, 21, 1061–1073.
29.
Tunçel, L. ( 1994). “Constant potential primal-dual algorithms: A framework.” Math. Programming, 66, 145–159.
30.
Van Slyke, R., and Wets, R. ( 1969). “L-shaped linear programs with application to optimal control and stochastic programming.” SIAM J. on Appl. Math., 17, 638–663.
31.
Watkins, D. W., and McKinney, D. C. (1997). “Finding robust solutions to water resources problems.”J. Water Resour. Plng. and Mgmt., ASCE, 123(1), 49–58.
32.
Wets, R. J.-B. ( 1983). “Solving stochastic programs with simple recourse.” Stochastics, 10, 219–242.
33.
Wets, R. J.-B. ( 1988). “Large scale linear programming techniques.” Numerical techniques for stochastic optimization, Y. S. Ermoliev and R. J.-B. Wets, eds., Springer, New York.
34.
Wright, S. J. ( 1997). “Primal-dual interior-point methods.” SIAM Publ. Ser., Philadelphia.
35.
Yakowitz, D. S. ( 1994). “A regularized algorithm for solving two-stage stochastic linear programming problems: A water resources example.” Stochastic and statistical modelling with ground water and surface water applications, K. W. Hipel, ed., Kluwer, Dordrecht, The Netherlands, Vol. 2, 271–284.
36.
Yeh, W. W.-G. ( 1985). “Reservoir management and operations models: A state-of-the-art review.” Water Resour. Res., 21(12), 1797–1818.
37.
Zhang, Y. ( 1995). Lipsol: a Matlab toolkit for linear programming, Dept. of Math. and Statistics, University of Maryland, Baltimore, Md., 〈http://math.umbc.edu/yzhang〉
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 127 • Issue 1 • February 2001
Pages: 48 - 57
History
Received: Apr 29, 1997
Published online: Feb 1, 2001
Published in print: Feb 2001
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.