Efficient Two-Phase Algorithm to Solve Nonconvex MINLP Model of Pump Scheduling Problem
Publication: Journal of Water Resources Planning and Management
Volume 147, Issue 8
Abstract
In water distribution networks, pumps are used to raise the pressure of water and transfer it throughout the network. Because the cost of electricity consumed by pumps is very high, optimal planning of pumping operations is of great importance. In this paper, the pump scheduling problem is formulated as a mixed integer nonlinear programming (MINLP) model assuming that the flow direction on pipes is not fixed in advance. Due to the hydraulic constraints, the model contains nonlinear terms as the square of continuous variables. Because of the nonconvexity, the MINLP solvers would be unable to find a feasible solution to the moderate- and large-sized instances of the problem in a reasonable time. In this paper, a two-phase method is presented to solve the problem. In the first phase, an initial feasible solution is generated via a heuristic method based on the underlying problem structure. This solution is then fed into the second phase to reach a near-optimal solution. The core part of this algorithm is an iterative approach based on the piecewise McCormick relaxation technique, and to accelerate the method, some techniques such as bound-tightening and the addition of valid inequalities are proposed. Computational experiments on some real-world instances taken from the literature confirm the efficiency of the proposed method compared to MINLP solvers from both solution quality and time.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
All data, models, and code that support the findings of this study are available from the corresponding author upon reasonable request.
Acknowledgments
We acknowledge Yorkshire Water Center of the University of Exeter, which provided the required data to draw Fig. 1. Additionally, we appreciate the valuable comments and suggestions from dear anonymous reviewers.
References
Abdallah, M., and Z. Kapelan. 2019. “Fast pump scheduling method for optimum energy cost and water quality in water distribution networks with fixed and variable speed pumps.” J. Water Resour. Plann. Manage. 145 (12): 04019055. https://doi.org/10.1061/(ASCE)WR.1943-5452.0001123.
Ali, N. A., G. Abozeid, M. D. Darweesh, and M. Mamdouh. 2016. “Simplification of water supply systems for producing more optimal pump schedules in less times.” J. Eng. Sci. 44 (4): 351–362.
Bene, J. G., I. Selek, and C. Hös. 2010. “Neutral search technique for short-term pump schedule optimization.” J. Water Resour. Plann. Manage. 136 (1): 133–137. https://doi.org/10.1061/(ASCE)0733-9496(2010)136:1(133).
Bergamini, M. L., P. Aguirre, and I. Grossmann. 2005. “Logic-based outer approximation for globally optimal synthesis of process networks.” Comput. Chem. Eng. 29 (9): 1914–1933. https://doi.org/10.1016/j.compchemeng.2005.04.003.
Burgschweiger, J., B. Gnädig, and M. C. Steinbach. 2005. “Nonlinear programming techniques for operative planning in large drinking water networks.” Open Appl. Math. J. 3: 14–28. https://doi.org/10.2174/1874114200903010014.
Castro, P. M. 2016. “Normalized multiparametric disaggregation: An efficient relaxation for mixed-integer bilinear problems.” J. Global Optim. 64 (4): 765–784. https://doi.org/10.1007/s10898-015-0342-z.
Cimorelli, L., A. D’Aniello, and L. Cozzolino. 2020. “Boosting genetic algorithm performance in pump scheduling problems with a novel decision-variable representation.” J. Water Resour. Plann. Manage. 146 (5): 04020023. https://doi.org/10.1061/(ASCE)WR.1943-5452.0001198.
Costa, L., B. Prata, H. M. Ramos, and M. Castro. 2016. “A branch-and-bound algorithm for optimal pump scheduling in water distribution networks.” Water Resour. Manage. 30 (3): 1037–1052. https://doi.org/10.1007/s11269-015-1209-2.
Cunha, M., J. Marques, E. Creaco, and D. Savić. 2019. “A dynamic adaptive approach for water distribution network design.” J. Water Resour. Plann. Manage. 145 (7): 04019026. https://doi.org/10.1061/(ASCE)WR.1943-5452.0001085.
D’Ambrosio, C., A. Lodi, S. Wiese, and C. Bragalli. 2015. “Mathematical programming techniques in water network optimization.” Eur. J. Oper. Res. 243 (3): 774–788. https://doi.org/10.1016/j.ejor.2014.12.039.
Exeter. 2020. “Centre for water systems.” Accessed August 1, 2019. http://emps.exeter.ac.uk/engineering/research/cws/resources/benchmarks/operation/richmond.php.
Faria, D. C., and M. J. Bagajewicz. 2012. “A new approach for global optimization of a class of MINLP problems with applications to water management and pooling problems.” AIChE 58 (8): 2320–2335. https://doi.org/10.1002/aic.12754.
GAMS Development Corporation. 2020. “GAMS Documentation.” Accessed March 26, 2021. http://www.gams.com.
Ghaddar, B., J. Naoum-Sawaya, A. Kishimoto, N. Taheri, and B. Eck. 2015. “A Lagrangian decomposition approach for the pump scheduling problem in water networks.” Eur. J. Oper. Res. 241 (2): 490–501. https://doi.org/10.1016/j.ejor.2014.08.033.
Giacomello, C., Z. Kapelan, and M. Nicolini. 2012. “Fast hybrid optimisation method for effective pump scheduling.” J. Water Resour. Plann. Manage. 139 (2): 175–183. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000239.
Giacomello, C., Z. Kapelan, and M. Nicolini. 2013. “Fast hybrid optimization method for effective pump scheduling.” J. Water Resour. Plann. Manage. 139 (2): 175–183. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000239.
Gleixner, A. M., H. Held, W. Huang, and S. Vigerske. 2012. “Towards globally optimal operation of water supply networks.” Numer. Algebra Control Optim. 2 (4): 695–711. https://doi.org/10.3934/naco.2012.2.695.
Hasan, M. F., and I. A. Karimi. 2010. “Piecewise linear relaxation of bilinear programs using bivariate partitioning.” AIChE 56 (7): 1880–1893. https://doi.org/10.1002/aic.12109.
Hooshmand, F., F. Amerehi, and S. A. MirHassani. 2020a. “Logic-based benders decomposition algorithm for contamination detection problem in water networks.” Comput. Oper. Res. 115 (Mar): 104840. https://doi.org/10.1016/j.cor.2019.104840.
Hooshmand, F., F. Amerehi, and S. A. MirHassani. 2020b. “Risk-based models for optimal sensor location problem on water networks.” J. Water Resour. Plann. Manage. 146 (11): 04020086. https://doi.org/10.1061/(ASCE)WR.1943-5452.0001293.
Jones, G. M., R. L. Sanks, B. E. Bosserman, and G. Tchobanoglous. 2006. Pumping station design. Houston: Gulf Professional Publishing.
Jowitt, P. W., and G. Germanopoulos. 1992. “Optimal pump scheduling in water-supply networks.” J. Water Resour. Plann. Manage. 118 (4): 406–422. https://doi.org/10.1061/(ASCE)0733-9496(1992)118:4(406).
Kumar, S. M., S. Narasimhan, and M. Bhallamudi. 2008. “State estimation in water distribution networks using graph-theoretic reduction strategy.” J. Water Resour. Plann. Manage. 134 (5): 395–403. https://doi.org/10.1061/(ASCE)0733-9496(2008)134:5(395).
Liberti, L., S. Cafieri, and F. Tarissan. 2009. “Reformulations in mathematical programming: A computational approach.” In Foundations of computational intelligence volume 3. Studies in computational intelligence, edited by A. Abraham, A. E. Hassanien, P. Siarry, and A. Engelbrecht. Berlin: Springer. https://doi.org/10.1007/978-3-642-01085-9_7.
López-Ibáñez, M., T. D. Prasad, and B. Paechter. 2008. “Ant colony optimization for optimal control of pumps in water distribution networks.” J. Water Resour. Plann. Manage. 134 (4): 337–346. https://doi.org/10.1061/(ASCE)0733-9496(2008)134:4(337).
Makaremi, Y., A. Haghighi, and H. R. Ghafouri. 2017. “Optimization of pump scheduling program in water supply systems using a self-adaptive NSGA-II; a review of theory to real application.” Water Resour. Manage. 31 (4): 1283–1304. https://doi.org/10.1007/s11269-017-1577-x.
McCormick, G. P. 1976. “Computability of global solutions to factorable nonconvex programs.” Math. Program. 10 (1): 147–175. https://doi.org/10.1007/BF01580665.
Menke, R., E. Abraham, P. Parpas, and I. Stoianov. 2016. “Exploring optimal pump scheduling in water distribution networks with branch and bound methods.” Water Resour. Manage. 30 (14): 5333–5349. https://doi.org/10.1007/s11269-016-1490-8.
MirHassani, S. A., and F. Hooshmand. 2019. Methods and models in mathematical programming. New York: Springer.
Nagarajan, H., M. Lu, S. Wang, R. Bent, and K. Sundar. 2019. “An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs.” J. Global Optim. 74 (4): 639–675. https://doi.org/10.1007/s10898-018-00734-1.
Naoum-Sawaya, J., B. Ghaddar, E. Arandia, and B. Eck. 2015. “Simulation-optimization approaches for water pump scheduling and pipe replacement problems.” Eur. J. Oper. Res. 246 (1): 293–306. https://doi.org/10.1016/j.ejor.2015.04.028.
Paluszczyszyn, D., P. Skworcow, and B. Ulanicki. 2015. “A tool for practical simplification of water networks models.” Procedia Eng. 119: 486–495. https://doi.org/10.1016/j.proeng.2015.08.871.
Price, E., and A. Ostfeld. 2013. “Iterative linearization scheme for convex nonlinear equations: Application to optimal operation of water distribution systems.” J. Water Resour. Plann. Manage. 139 (3): 299–312. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000275.
Price, E., and A. Ostfeld. 2016. “Optimal pump scheduling in water distribution systems using graph theory under hydraulic and chlorine constraints.” J. Water Resour. Plann. Manage. 142 (10): 04016037. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000680.
Reca, J., A. García-Manzano, and J. Martínez. 2014. “Optimal pumping scheduling for complex irrigation water distribution systems.” J. Water Resour. Plann. Manage. 140 (5): 630–637. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000360.
Rossman, L. A. 2000. EPANET 2 user’s manual. Cincinnati, OH: EPA.
Sakarya, A. B. A., and L. W. Mays. 2000. “Optimal operation of water distribution pumps considering water quality.” J. Water Resour. Plann. Manage. 126 (4): 210–220. https://doi.org/10.1061/(ASCE)0733-9496(2000)126:4(210).
Shi, H., and F. You. 2016. “Energy optimization of water supply system scheduling: Novel MINLP model and efficient global optimization algorithm.” AIChE 62 (12): 4277–4296. https://doi.org/10.1002/aic.15332.
Singh, M. K., and V. Kekatos. 2019. “Optimal scheduling of water distribution systems.” IEEE Trans. Control Network Syst. 7 (2): 711–723. https://doi.org/10.1109/TCNS.2019.2939651.
Teles, J. P., P. M. Castro, and H. A. Matos. 2012. “Global optimization of water networks design using multiparametric disaggregation.” Comput. Chem. Eng. 40 (May): 132–147. https://doi.org/10.1016/j.compchemeng.2012.02.018.
Teles, J. P., P. M. Castro, and H. A. Matos. 2013a. “Multi-parametric disaggregation technique for global optimization of polynomial programming problems.” J. Global Optim. 55 (2): 227–251. https://doi.org/10.1007/s10898-011-9809-8.
Teles, J. P., P. M. Castro, and H. A. Matos. 2013b. “Univariate parameterization for global optimization of mixed-integer polynomial problems.” Eur. J. Oper. Res. 229 (3): 613–625. https://doi.org/10.1016/j.ejor.2013.03.042.
van Zyl, J. E., D. A. Savic, and G. Walters. 2004. “Operational optimization of water distribution systems using a hybrid genetic algorithm.” J. Water Resour. Plann. Manage. 130 (2): 160–170. https://doi.org/10.1061/(ASCE)0733-9496(2004)130:2(160).
Verleye, D., and E. H. Aghezzaf. 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. https://doi.org/10.1080/00207543.2013.850550.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 147 • Issue 8 • August 2021
Copyright
© 2021 American Society of Civil Engineers.
History
Received: Aug 19, 2020
Accepted: Jan 7, 2021
Published online: May 27, 2021
Published in print: Aug 1, 2021
Discussion open until: Oct 27, 2021
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.
Cited by
- Baigang Du, Dahu Zha, Jun Guo, Xiaobing Yu, Optimization of pump scheduling in waterworks considering load balancing using improved genetic algorithm, Journal of Intelligent & Fuzzy Systems, 10.3233/JIFS-224245, (1-19), (2023).