Generalized Benders Decomposition to Reoptimize Water Production and Distribution Operations in a Real Water Supply Network
Publication: Journal of Water Resources Planning and Management
Volume 142, Issue 2
Abstract
Water supply networks are designed to effectively and efficiently supply water to some originally targeted agglomerations. However, the dynamics over time of water-demand patterns and electricity cost schemes may render these designs inefficient and expensive to operate. This paper considers the challenging problem of optimizing water production and distribution operations in one of the largest water supply networks operating in Flanders (Belgium) while accounting for the water-demand and electricity cost dynamics. Optimizing operations in a real water supply network is a difficult task as it involves many constraints. In addition to the complex hydraulic nonlinear equality constraints stemming from friction losses and pump curves, specific constraints for accurate modeling of storage buffers must be taken into account. These constraints require additional binary variables to model free inflow or possible reinjection of water to the network. The resulting optimization problem is thus a nonconvex mixed-integer and nonlinear mathematical problem that is computationally expensive to solve. A particularly appealing method for solving such optimization problems is Generalized Benders Decomposition (GBD). This paper extends this method to the water supply network optimization problem mentioned previously. It is experimentally shown that the approach is successful through careful selection of the complicating variables and values for the penalty term. Results of the experiments carried out on two network instances show that the carefully fine-tuned model allows convergence to near-optimal solutions. Compared to state-of-the-art solvers, the proposed approach proved to be competitive on the tested networks in terms of solution quality and computational time.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This research is funded by a Ph.D. grant of the Agency for Innovation by Science and Technology (IWT). This support is highly appreciated.
References
Bagajewicz, M. J., and Manousiouthakis, V. (1991). “On the generalized Benders decomposition.” Comput. Chem. Eng., 15(10), 691–700.
Benders, J. (1962). “Partitioning procedures for solving mixed-variables programming problems.” Numerische Mathematik, 4(1), 238–252.
Bi, W., and Dandy, G. (2014). “Optimization of water distribution systems using online retrained metamodels.” J. Water Resour. Plann. Manage., 04014032.
Bonami, P., et al. (2008). “An algorithmic framework for convex mixed integer nonlinear programs.” Discrete Optim., 5(2), 186–204.
Bounds, P., Kahler, J., and Ulanicki, B. (2006). “Efficient energy management of a large-scale water supply system.” Civ. Eng. Environ. Syst., 23(3), 209–220.
Brook, A., Kendrick, D., and Meeraus, A. (1988). GAMS—A user’s guide, Scientific Press, Redwood City, CA.
Burgschweiger, J., Gnädig, B., and Steinbach, M. C. (2009). “Nonlinear programming techniques for operative planning in large drinking water networks.” Open Appl. Math. J., 3, 14–28.
Burgschweiger, J., Gnädig, B., and Steinbach, M. C. (2009). “Optimization models for operative planning in drinking water networks.” Optim. Eng., 10(1), 43–73.
Cai, X., McKinney, D. C., Lasdon, L. S., and Watkins, D. (2001). “Solving large nonconvex water resources management models using generalized Benders decomposition.” Oper. Res., 49(2), 235–245.
Can, E., and Houck, M. (1984). “Real-time reservoir operations by goal programming.” J. Water Resour. Plann. Manage, 297–309.
Cembrano, G., Wells, G., Quevedo, J., Pérez, R., and Argelaguet, R. (2000). “Optimal control of a water distribution network in a supervisory control system.” Control Eng. Pract., 8(10), 1177–1188.
Cohen, D., Shamir, U., and Sinai, G. (2004). “Sensitivity analysis of optimal operation of irrigation supply systems with water quality considerations.” Irrig. Drain. Syst., 18(3), 227–253.
Coulbeck, B., Brdys, M., Orr, C. H., and Rance, J. P. (1988a). “A hierarchical approach to optimized control of water distribution systems: Part I. Decomposition.” Optim. Control Appl. Meth., 9(1), 51–61.
Coulbeck, B., Brdys, M., Orr, C. H., and Rance, J. P. (1988b). “A hierarchical approach to optimized control of water distribution systems: Part II. Lower-level algorithm.” Optim. Control Appl. Meth., 9(2), 109–126.
Crawley, P. D., and Dandy, G. C. (1993). “Optimal operation of multiple-reservoir system.” J. Water Resour. Plann. Manage., 1–17.
D’Ambrosio, C., Lodi, A., Wiese, S., and Bragalli, C. (2015). “Mathematical programming techniques in water network optimization.” Eur. J. Oper. Res, 243(3), 774–788.
De Corte, A., and Sörensen, K. (2012). “Optimisation of gravity-fed water distribution network design: A critical review.” Eur. J. Oper. Res, 228(1), 1–10.
Diba, A., Louie, P. W. F., Mahjoub, M., and Yeh, W. W.-G. (1995). “Planned operation of large-scale water-distribution system.” J. Water Resour. Plann. Manage., 260–269.
Ernst, A. T. (1996). “Continuous time quadratic cost flow problems with applications to water distribution networks.” J. Aust. Math. Soc. Ser. B Appl. Math., 37(4), 530–548.
Floudas, C. A. (1995). Nonlinear and mixed-integer optimization: Fundamentals and applications, Oxford University Press, Oxford, U.K.
Fourer, R., Gay, D. M., and Kernighan, B. W. (1990). “A modelling language for mathematical programming.” Manage. Sci., 36(5), 519–554.
Geoffrion, A. M. (1972). “Generalised Benders decomposition.” J. Optim. Theory Appl, 10(4), 237–260.
Guhl, F. (1999). “Gestion optimal des réseaux d’eau potable.” Ph.D. thesis, Univ. Louis Pasteur (in French), Strasbourg, France.
Gurobi Optimization. (2014). Gurobi optimizer reference manual version 6.0, Houston.
Lansey, K. E., and Awumah, K. (1994). “Optimal pump operations considering pump switches.” J. Water Resour. Plann. Manage, 17–35.
López-Ibáñez, M., Prasad, T. D., and Paechter, B. (2008). “Ant colony optimization for optimal control of pumps in water distribution networks.” J. Water Resour. Plann. Manage., 337–346.
Murtagh, B. A., and Saunders, M. A. (1978). “Large-scale linearly constrained optimization.” Math. Program., 14(1), 41–72.
Nicklow, J., et al. (2010). “State of the art for genetic algorithms and beyond in water resources planning and management.” J. Water Resour. Plann. Manage., 412–432.
Nitivattananon, V., Sadowski, E. C., and Quimpo, R. G. (1996). “Optimization of water supply system operation.” J. Water Resour. Plann. Manage., 374–384.
Ormsbee, L., and Lansey, K. (1994). “Optimal control of water supply pumping systems.” J. Water Resour. Plann. Manage., 237–252.
Pasha, M. F. K., and Lansey, K. (2009). “Optimal pump scheduling by linear programming.” World Environmental and Water Resources Congress 2009, ASCE, Reston, VA.
Pezeshk, S., Helweg, O. J., and Oliver, K. E. (1994). “Optimal operation of ground-water supply distribution systems.” J. Water Resour. Plann. Manage., 573–586.
Rossman, L. A. (2000). EPANET 2 users manual, U.S. Environmental Protection Agency, Cincinnati.
Sahinidis, N., and Grossmann, I. (1991). “Convergence properties of generalized Benders decomposition.” Comput. Chem. Eng., 15(7), 481–491.
Savic, D. A., and Walters, G. A. (1997). “Genetic algorithms for least-cost design of water distribution networks.” J. Water Resour. Plann. Manage., 67–77.
Shamir, U., and Salomons, E. (2008). “Optimal real-time operation of urban water distribution systems using reduced models.” J. Water Resour. Plann. Manage., 181–185.
Sun, Y.-H., Yeh, W. W.-G., Hsu, N.-S., and Louie, P. W. F. (1995). “Generalized network algorithm for water-supply-system optimization.” J. Water Resour. Plann. Manage., 392–398.
Verleye, D., and Aghezzaf, E.-H. (2013). “Optimising production and distribution operations in large water supply networks: A piecewise linear optimisation approach.” Int. J. Prod. Res., 51(23–24), 7170–7189.
Vieira, J., et al. (2011). “Optimization of the operation of large-scale multisource water-supply systems.” J. Water Resour. Plann. Manage., 150–161.
Watkins, D. W., and McKinney, D. C. (1998). “Decomposition methods for water resources optimization models with fixed costs.” Adv. Water Resour., 21(4), 283–295.
Zessler, U., and Shamir, U. (1989). “Optimal operation of water distribution systems.” J. Water Resour. Plann. Manage., 735–752.
Information & Authors
Information
Published In
Copyright
© 2015 American Society of Civil Engineers.
History
Received: Mar 5, 2015
Accepted: Aug 11, 2015
Published online: Oct 15, 2015
Published in print: Feb 1, 2016
Discussion open until: Mar 15, 2016
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.