×

zbMATH — the first resource for mathematics

Global optimality bounds for the placement of control valves in water supply networks. (English) Zbl 1430.90434
Summary: This manuscript investigates the problem of optimal placement of control valves in water supply networks, where the objective is to minimize average zone pressure. The problem formulation results in a nonconvex mixed integer nonlinear program (MINLP). Due to its complex mathematical structure, previous literature has solved this nonconvex MINLP using heuristics or local optimization methods, which do not provide guarantees on the global optimality of the computed valve configurations. In our approach, we implement a branch and bound method to obtain certified bounds on the optimality gap of the solutions. The algorithm relies on the solution of mixed integer linear programs, whose formulations include linear relaxations of the nonconvex hydraulic constraints. We investigate the implementation and performance of different linear relaxation schemes. In addition, a tailored domain reduction procedure is implemented to tighten the relaxations. The developed methods are evaluated using two benchmark water supply networks and an operational water supply network from the UK. The proposed approaches are shown to outperform state-of-the-art global optimization solvers for the considered benchmark water supply networks. The branch and bound algorithm converges to good quality feasible solutions in most instances, with bounds on the optimality gap that are comparable to the level of parameter uncertainty usually experienced in water supply network models.
MSC:
90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C90 Applications of mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abraham, E.; Blokker, M.; Stoianov, I., Decreasing the discoloration risk of drinking water distribution systems through optimized topological changes and optimal flow velocity control, J Water Resour Plan Manag, 144, 04017093, (2018)
[2] Ali, ME, Knowledge-based optimization model for control valve locations in water distribution networks, J Water Resour Plan Manag, 141, 04014048, (2015)
[3] Araujo, LS; Ramos, H.; Coelho, ST, Pressure control for leakage minimisation in water distribution systems management, Water Resour Manag, 20, 133-149, (2006)
[4] Belotti, P., Bound reduction using pairs of linear inequalities, J Glob Optim, 56, 787-819, (2013) · Zbl 1272.90033
[5] Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tightening techniques for non-convex MINLP, Optim Methods Softw, 24, 597-634, (2009) · Zbl 1179.90237
[6] Bonami, P.; Biegler, LT; Conn, AR; Cornuéjols, G.; Grossmann, IE; Laird, CD; Lee, J.; Lodi, A.; Margot, F.; Sawaya, N.; Wächter, A., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim, 5, 186-204, (2008) · Zbl 1151.90028
[7] Bragalli, C.; D’Ambrosio, C.; Lee, J.; Lodi, A.; Toth, P., On the optimal design of water distribution networks: a practical MINLP approach, Optim Eng, 13, 219-246, (2012) · Zbl 1293.76045
[8] Currie J, Wilson DI (2012) OPTI: lowering the barrier between open source optimizers and the industrial MATLAB user. In: Foundations of computer-aided process operations. https://www.inverseproblem.co.nz/OPTI/. Accessed 27 Nov 2018
[9] Dai, PD; Li, P., Optimal localization of pressure reducing valves in water distribution systems by a reformulation approach, Water Resour Manag, 28, 3057-3074, (2014)
[10] Paola, F.; Galdiero, E.; Giugni, M., Location and setting of valves in water distribution networks using a harmony search approach, J Water Resour Plan Manag, 143, 04017015, (2017)
[11] Deuerlein, J., Decomposition model of a general water supply network graph, J Hydraul Eng, 134, 822-832, (2008)
[12] Diamond, S.; Takapoui, R.; Boyd, S., A general system for heuristic minimization of convex functions over non-convex sets, Optim Methods Softw, 33, 165-193, (2018) · Zbl 1386.90182
[13] DAmbrosio, C.; Lodi, A.; Wiese, S.; Bragalli, C., Mathematical programming techniques in water network optimization, Eur J Oper Res, 243, 774-788, (2015) · Zbl 1346.90211
[14] Eck BJ, Mevissen M (2012) Non-linear optimization with quadratic pipe friction. Technical report RC25307. IBM Research Division
[15] Eck BJ, Mevissen M (2013) Fast non-linear optimization for design problems on water networks. In: World environmental and water resources congress 2013. American Society of Civil Engineers, Reston, VA, pp 696-705
[16] Elhay, S.; Simpson, AR; Deuerlein, J.; Alexander, B.; Schilders, W., A reformulated co-tree flows method competitive with the global Gradient Algorithm for solving the water distribution system equations, J Water Resour Plan Manag, 140, 04014040, (2014)
[17] Gamrath G, Fischer T, Gally T, Gleixner A, Hendel G, Koch T, Maher SJ, Miltenberger M, Muller B, Pfetsch ME, Puchert C, Rehfeldt D, Schenker S, Schwarz R, Serrano F, Shinano Y, Vigerske S, Weninger D, Winkler M, Witt JT, Witzig J (2016) The SCIP optimization suite 3.2. Technical report 15-60, Zuse Institute, Berlin
[18] Gleixner, A.; Held, H.; Huang, W.; Vigerske, S., Towards globally optimal operation of water supply networks, Numer Algebra Control Optim, 2, 695-711, (2012) · Zbl 1269.90083
[19] Gurobi Optimization (2017) Gurobi optimizer reference manual. https://www.gurobi.com/documentation/7.5/refman.pdf. Accessed 27 Nov 2018
[20] Hindi, KS; Hamam, YM, Locating pressure control elements for leakage minimization in water supply networks: an optimization model, Eng Optim, 17, 281-291, (1991)
[21] Humpola, J.; Fügenschuh, A., Convex reformulations for solving a nonlinear network design problem, Comput Optim Appl, 62, 717-759, (2015) · Zbl 1337.90072
[22] Humpola, J.; Fügenschuh, A.; Koch, T., Valid inequalities for the topology optimization problem in gas network design, OR Spectr, 38, 597-631, (2016) · Zbl 1372.90023
[23] Jowitt, PW; Xu, C., Optimal valve control in water distribution networks, J Water Resour Plan Manag, 116, 455-472, (1990)
[24] Kolodziej, S.; Castro, PM; Grossmann, IE, Global optimization of bilinear programs with a multiparametric disaggregation technique, J Glob Optim, 57, 1039-1063, (2013) · Zbl 1282.90137
[25] Klnç, MR; Sahinidis, NV, Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON, Optim Methods Softw, 33, 540-562, (2018) · Zbl 1398.90110
[26] Lambert A (2000) What do we know about pressure: leakage relationships in distribution. systems? In: IWA conference system approach to leakage control and water distribution systems management. IWA
[27] Lambert, A.; Thornton, J., The relationships between pressure and bursts a state-of-the-art update, Water21 Mag Int Water Assoc, 21, 37-38, (2011)
[28] Liberatore, S.; Sechi, GM, Location and calibration of valves in water distribution networks using a scatter-search meta-heuristic approach, Water Resour Manag, 23, 1479-1495, (2009)
[29] Liberti, L.; Pantelides, CC, Convex envelopes of monomials of odd degree, J Glob Optim, 25, 157-168, (2003) · Zbl 1030.90117
[30] Menke, R.; Abraham, E.; Parpas, P.; Stoianov, I., Exploring optimal pump scheduling in water distribution networks with branch and bound, Water Resour Manag, 30, 5333-5349, (2015)
[31] Misener, R.; Floudas, CA, GloMIQO: global mixed-integer quadratic optimizer, J Glob Optim, 57, 3-50, (2013) · Zbl 1272.90034
[32] Misener, R.; Floudas, CA, ANTIGONE: Algorithms for coNTinuous/Integer Global Optimization of Nonlinear Equations, J Glob Optim, 59, 503-526, (2014) · Zbl 1301.90063
[33] Nicolini, M.; Zovatto, L., Optimal location and control of pressure reducing valves in water networks, J Water Resour Plan Manag, 135, 178-187, (2009)
[34] Pecci, F.; Abraham, E.; Stoianov, I., Outer approximation methods for the solution of co-design optimisation problems in water distribution networks, IFAC-PapersOnLine, 50, 5373-5379, (2017)
[35] Pecci, F.; Abraham, E.; Stoianov, I., Penalty and relaxation methods for the optimal placement and operation of control valves in water supply networks, Comput Optim Appl, 67, 201-223, (2017) · Zbl 1375.90227
[36] Pecci, F.; Abraham, E.; Stoianov, I., Quadratic head loss approximations for optimisation of problems in water supply networks, J Hydroinform, 19, 493-506, (2017) · Zbl 1375.90227
[37] Pfetsch, ME; Fügenschuh, A.; Geißler, B.; Geißler, N.; Gollmer, R.; Hiller, B.; Humpola, J.; Koch, T.; Lehmann, T.; Martin, A.; Morsi, A.; Rövekamp, J.; Schewe, L.; Schmidt, M.; Schultz, R.; Schwarz, R.; Schweiger, J.; Stangl, C.; Steinbach, MC; Vigerske, S.; Willert, BM, Validation of nominations in gas network optimization: models, methods, and solutions, Optim Methods Softw, 30, 15-53, (2015) · Zbl 1325.90019
[38] Puranik, Y.; Sahinidis, NV, Domain reduction techniques for global NLP and MINLP optimization, Constraints, 22, 338-376, (2017) · Zbl 1387.90164
[39] Raghunathan, AU, Global optimization of nonlinear network design, SIAM J Optim, 23, 268-295, (2013) · Zbl 1270.90036
[40] Reis, LFR; Porto, RM; Chaudhry, FH, Optimal location of control valves in pipe networks by genetic algorithm, J Water Resour Plan Manag, 123, 317-326, (1997)
[41] Sahinidis N (2018) BARON user manual v:18.8.23
[42] Sherali, HD; Subramanian, S.; Loganathan, G., Effective relaxation and partitioning schemes for solving water distribution network design problems to global optimality, J Glob Optim, 19, 1-26, (1999) · Zbl 0967.90087
[43] Smith, EMB; Pantelides, CC, A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs, Comput Chem Eng, 23, 457-478, (1999)
[44] Tawarmalani M, Sahinidis NV (2002) Convexification and global optimization in continuous and mixed-integer nonlinear programming, 1st, edn. edn. Springer, New York. https://doi.org/10.1007/978-1-4757-3532-1 · Zbl 1031.90022
[45] Udell M, Boyd S (2015) Maximizing a sum of sigmoids. http://web.stanford.edu/ boyd/papers/pdf/max_sum_sigmoids.pdf. Accessed 27 Nov 2018
[46] Vigerske S (2012) Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming. PhD thesis, Humboldt-Universität zu, Berlin
[47] Waechter, A.; Biegler, LT, On the implementation of a primal – dual interior point filter line search algorithm for large-scale nonlinear programming, Math Program, 106, 25-57, (2006) · Zbl 1134.90542
[48] Wright, R.; Stoianov, I.; Parpas, P.; Henderson, K.; King, J., Adaptive water distribution networks with dynamically reconfigurable topology, J Hydroinform, 16, 1280-1301, (2014)
[49] Wright, R.; Abraham, E.; Parpas, P.; Stoianov, I., Control of water distribution networks with dynamic DMA topology using strictly feasible sequential convex programming, Water Resour Res, 51, 99259941, (2015)
[50] Zamora, JM; Grossmann, IE, A global MINLP optimization algorithm for the synthesis of heat exchanger networks with no stream splits, Comput Chem Eng, 22, 367-384, (1998)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.