Model Reduction and Outer Approximation for Optimizing the Placement of Control Valves in Complex Water Networks
Publication: Journal of Water Resources Planning and Management
Volume 145, Issue 5
Abstract
The optimal placement and operation of pressure control valves in water distribution networks is a challenging engineering problem. When formulated in a mathematical optimization framework, this problem results in a nonconvex mixed integer nonlinear program (MINLP), which has combinatorial computational complexity. As a result, the considered MINLP becomes particularly difficult to solve for large-scale looped operational networks. We extend and combine network model reduction techniques with the proposed optimization framework in order to lower the computational burden and enable the optimal placement and operation of control valves in these complex water distribution networks. An outer approximation algorithm is used to solve the considered MINLPs on reduced hydraulic models. We demonstrate that the restriction of the considered optimization problem on a reduced hydraulic model is not equivalent to solving the original larger MINLP, and its solution is therefore sub-optimal. Consequently, we investigate the trade-off between reducing computational complexity and the potential sub-optimality of the solutions that can be controlled with a parameter of the model reduction routine. The efficacy of the proposed method is evaluated using two large scale water distribution network models.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This research was supported by the NEC-Imperial Smart Water Systems project and EPSRC Fellowship on Dynamically Adaptive and Resilient Water Supply Networks for a Sustainable Future (EP/P004229/1). We thank Cla-Val and Bristol Water for their support in the implementation and operation of the Field Lab (Smart Water Network Demonstrator).
References
Ali, M. E. 2015. “Knowledge-based optimization model for control valve locations in water distribution networks.” J. Water Resour. Plann. Manage. 141 (1): 04014048. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000438.
Burgschweiger, J., B. Gnädig, and M. C. Steinbach. 2005. “Nonlinear programming techniques for operative planning in large drinking water networks.”. Berlin: Zuse-Institute Berlin.
Creaco, E., D. Ph, and G. Pezzinga. 2015. “Multiobjective optimization of pipe replacements and control valve installations for leakage attenuation in water distribution networks.” J. Water Resour. Plann. Manage. 141 (3): 04014059. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000458.
Currie, J., and D. I. Wilson. 2012. “OPTI: Lowering the barrier between open source optimizers and the industrial MATLAB user.” Foundations of Computer-Aided Process Operations. Accessed January 30, 2019. http://www.i2c2.aut.ac.nz/Wiki/OPTI/index.php.
Dai, P. D., and P. Li. 2014. “Optimal localization of pressure reducing valves in water distribution systems by a reformulation approach.” Water Resour. Manage. 28 (10): 3057–3074. https://doi.org/10.1007/s11269-014-0655-6.
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.
De Paola, F., E. Galdiero, and M. Giugni. 2017. “Location and setting of valves in water distribution networks using a harmony search approach.” J. Water Resour. Plann. Manage. 143 (6): 04017015. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000760.
Deuerlein, J. 2008. “Decomposition model of a general water supply network graph.” J. Hydraul. Eng. 134 (6): 822–832. https://doi.org/10.1061/(ASCE)0733-9429(2008)134:6(822).
Deuerlein, J., S. Elhay, and A. R. Simpson. 2016. “Fast graph partitioning algorithm for solving the water distribution systems equations.” J. Water Resour. Plann. Manage. 142 (1): 04015037. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000561.
Eck, B. J., and M. Mevissen. 2012. “Non-linear optimization with quadratic pipe friction.”. Dublin, Ireland: IBM Research Division.
Eck, B. J., and M. Mevissen. 2015. “Quadratic approximations for pipe friction.” J. Hydroinf. 17 (3): 462–472. https://doi.org/10.2166/hydro.2014.170.
Elhay, S., A. R. Simpson, J. Deuerlein, B. Alexander, and W. Schilders. 2014. “A reformulated co-tree flows method competitive with the global gradient algorithm for solving the water distribution system equations.” J. Water Resour. Plann. Manage. 140 (12): 04014040. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000431.
Floudas, C. A. 1995. Nonlinear and mixed-integer optimization: Fundamentals and applications. New York: Oxford University Press.
Gamrath, G., et al. 2016. The SCIP Optimization Suite 3.2. Berlin: Zuse Institute Berlin.
Gurobi Optimization. 2017. “Gurobi optimizer reference manual.” Accessed January 30, 2019. https://www.gurobi.com/documentation/7.5/refman.pdf.
Kocis, G. R., and I. E. Grossmann. 1987. “Relaxation strategy for the structural optimization of process flow sheets.” Ind. Eng. Chem. Res. 26 (9): 1869–1880. https://doi.org/10.1021/ie00069a026.
Lambert, A. 2000. “What do we know about pressure: Leakage relationships in distribution systems?.” In Proc., IWA Conf. system approach to leakage control and water distribution systems management. London: International Water Association.
Lambert, A., and J. Thornton. 2011. “The relationships between pressure and bursts a state-of-the-art update.” Water 21: 37–38.
Liberti, L. 2012. “Reformulations in mathematical programming: Automatic symmetry detection and exploitation.” Math. Program. 131 (1–2): 273–304. https://doi.org/10.1007/s10107-010-0351-0.
Margot, F. 2010. “Symmetry in integer linear programming.” Chap. 17 in 50 years of integer programming 1958–2008: From the early years to the state-of-the-art, 547–686. Berlin: Springer.
Nicolini, M., and L. Zovatto. 2009. “Optimal location and control of pressure reducing valves in water networks.” J. Water Resour. Plann. Manage. 135 (3): 178–187. https://doi.org/10.1061/(ASCE)0733-9496(2009)135:3(178).
Ostfeld, A., et al. 2008. “The Battle of the Water Sensor Networks (BWSN): A design challenge for engineers an algorithms.” J. Water Resour. Plann. Manage. 134 (6): 556–568. https://doi.org/10.1061/(ASCE)0733-9496(2008)134:6(556).
Paluszczyszyn, D., P. Skworcow, and B. Ulanicki. 2013. “Online simplification of water distribution network models for optimal scheduling.” J. Hydroinf. 15 (3): 652–665. https://doi.org/10.2166/hydro.2013.029.
Pecci, F., E. Abraham, and I. Stoianov. 2017a. “Outer approximation methods for the solution of co-design optimisation problems in water distribution networks.” IFAC-PapersOnLine 50 (1): 5373–5379. https://doi.org/10.1016/j.ifacol.2017.08.1069.
Pecci, F., E. Abraham, and I. Stoianov. 2017b. “Penalty and relaxation methods for the optimal placement and operation of control valves in water supply networks.” Comput. Optim. Appl. 67 (1): 201–223. https://doi.org/10.1007/s10589-016-9888-z.
Pecci, F., E. Abraham, and I. Stoianov. 2017c. “Quadratic head loss approximations for optimisation of problems in water supply networks.” J. Hydroinf. 19 (4): 493–506. https://doi.org/10.2166/hydro.2017.080.
Pecci, F., E. Abraham, and I. Stoianov. 2017d. “Scalable Pareto set generation for multiobjective co-design problems in water distribution networks: A continuous relaxation approach.” Struct. Multidiscip. Optim. 55 (3): 857–869. https://doi.org/10.1007/s00158-016-1537-8.
Ralphs, T. K., Y. Shinano, T. Berthold, and T. Koch. 2018. “Parallel solvers for mixed integer linear optimization.” In Handbook of parallel constraint reasoning, edited by Y. Hamadi and L. Sais. Cham, Switzerland: Springer.
Simpson, A. R., S. Elhay, and B. Alexander. 2014. “Forest-core partitioning algorithm for speeding up analysis of water distribution systems.” J. Water Resour. Plann. Manage. 140 (4): 435–443. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000336.
Ulanicki, B., A. Zehnpfund, and F. Martinez. 1996. “Simplification of water distribution network models.” In Proc., 2nd Int. Conf. on Hydroinformatics, 493–500. Rotterdam, Netherlands: A.A. Balkema.
Viswanathan, J., and I. E. Grossmann. 1990. “A combined penalty function and outer-approximation method for MINLP optimization.” Comput. Chem. Eng. 14 (7): 769–782. https://doi.org/10.1016/0098-1354(90)87085-4.
Waechter, A., and L. T. Biegler. 2006. “On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming.” Math. Program. 106 (1): 25–57. https://doi.org/10.1007/s10107-004-0559-y.
Wright, R., E. Abraham, P. Parpas, and I. Stoianov. 2015. “Control of water distribution networks with dynamic DMA topology using strictly feasible sequential convex programming.” Water Resour. Res. 51 (12): 99259941. https://doi.org/10.1002/2015WR017466.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 145 • Issue 5 • May 2019
Copyright
©2019 American Society of Civil Engineers.
History
Received: Jan 17, 2018
Accepted: Oct 9, 2018
Published online: Feb 27, 2019
Published in print: May 1, 2019
Discussion open until: Jul 27, 2019
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.