×

Bi-objective design-for-control of water distribution networks with global bounds. (English) Zbl 1492.90166

Summary: This manuscript investigates the design-for-control (DfC) problem of minimizing pressure induced leakage and maximizing resilience in existing water distribution networks. The problem consists in simultaneously selecting locations for the installation of new valves and/or pipes, and optimizing valve control settings. This results in a challenging optimization problem belonging to the class of non-convex bi-objective mixed-integer non-linear programs (BOMINLP). In this manuscript, we propose and investigate a method to approximate the non-dominated set of the DfC problem with guarantees of global non-dominance. The BOMINLP is first scalarized using the method of \(\epsilon \)-constraints. Feasible solutions with global optimality bounds are then computed for the resulting sequence of single-objective mixed-integer non-linear programs, using a tailored spatial branch-and-bound (sBB) method. In particular, we propose an equivalent reformulation of the non-linear resilience objective function to enable the computation of global optimality bounds. We show that our approach returns a set of potentially non-dominated solutions along with guarantees of their non-dominance in the form of a superset of the true non-dominated set of the BOMINLP. Finally, we evaluate the method on two case study networks and show that the tailored sBB method outperforms state-of-the-art global optimization solvers.

MSC:

90C29 Multi-objective and goal programming
90C26 Nonconvex programming, global optimization
90C11 Mixed integer programming
90C90 Applications of mathematical programming

Software:

OPTI; SCIP; Gurobi; Ipopt; NBI; GloMIQO

References:

[1] Abraham, E.; Stoianov, I., Sparse null space algorithms for hydraulic analysis of large-scale water supply networks, J Hydraul Eng, 142, 3, 04015058 (2016) · doi:10.1061/(asce)hy.1943-7900.0001089
[2] Alvisi, S., A new procedure for optimal design of district metered areas based on the multilevel balancing and refinement algorithm, Water Resour Manag, 29, 12, 4397-4409 (2015) · doi:10.1007/s11269-015-1066-z
[3] Alvisi, S.; Franchini, M., Multiobjective optimization of rehabilitation and leakage detection scheduling in water distribution systems, J Water Resour Plan Manag, 135, 6, 426-439 (2009) · doi:10.1061/(ASCE)0733-9496(2009)135
[4] Atkinson, S.; Farmani, R.; Fa, Memon; Butler, D., Reliability indicators for water distribution system design: comparison, Water Resour Plan Manag, 140, 2, 160-168 (2014) · doi:10.1061/(ASCE)WR.1943-5452.0000304
[5] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numer, 22, 2013, 1-131 (2013) · Zbl 1291.65172 · doi:10.1017/S0962492913000032
[6] Bragalli C, D’Ambrosio C, Lee J, Lodi A, Toth P (2008) Water network design by MINLP. Report No. RC24495. Tech. rep., IBM Research Report
[7] Burachik, RS; Kaya, CY; Rizvi, MM, A new scalarization technique and new algorithms to generate pareto fronts, SIAM J Optim, 27, 2, 1010-1034 (2017) · Zbl 1370.90239 · doi:10.1137/16M1083967
[8] Burachik RS, Kaya CY, Rizvi MM (2019) Algorithms for generating pareto fronts of multi-objective integer and mixed-integer programming problems, pp 1-23. arXiv preprint arXiv:1903.07041
[9] Cacchiani, V.; D’Ambrosio, C., A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs, Eur J Oper Res, 260, 3, 920-933 (2017) · Zbl 1403.90597 · doi:10.1016/j.ejor.2016.10.015
[10] Castro, PM; Grossmann, IE, Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems, J Glob Optim, 59, 2-3, 277-306 (2014) · Zbl 1298.90058 · doi:10.1007/s10898-014-0162-6
[11] Charnes, A.; Cooper, WW, Programming with linear fractional functionals, Nav Res Logist Q, 9, 3-4, 181-186 (1962) · Zbl 0127.36901 · doi:10.1002/nav.3800090303
[12] Creaco, E.; Franchini, M.; Todini, E., The combined use of resilience and loop diameter uniformity as a good indirect measure of network reliability, Urban Water J, 13, 2, 167-181 (2016) · doi:10.1080/1573062X.2014.949799
[13] Cunha, M.; Marques, J., A new multiobjective simulated annealing AlgorithmMOSA-GR: application to the optimal design of water distribution networks, Water Resour Res (2020) · doi:10.1029/2019WR025852
[14] Currie, J.; Wilson, DI; Sahinidis, N.; Pinto, J., OPTI: lowering the barrier between open source optimizers and the industrial MATLAB user, Found Comput Aided Process Oper, 24, 1-6 (2012) · Zbl 1291.65172 · doi:10.1017/S0962492913000032
[15] Dai, PD; Li, P., Optimal localization of pressure reducing valves in water distribution systems by a reformulation approach, Water Resour Manag, 28, 10, 3057-3074 (2014) · doi:10.1007/s11269-014-0655-6
[16] D’Ambrosio, C.; Lodi, A.; Wiese, S.; Bragalli, C., Mathematical programming techniques in water network optimization, Eur J Oper Res, 243, 3, 774-788 (2015) · Zbl 1346.90211 · doi:10.1016/j.ejor.2014.12.039
[17] Das I (2000) Applicability of existing continuous methods in determining the Pareto set for nonlinear, mixed-integer multicriteria optimization problems. In: 8th Symposium on multidisciplinary analysis and optimization, p 4894. doi:10.2514/6.2000-4894
[18] Das, I.; Dennis, JE, Normal-boundary intersection: a new method for generating the pareto surface in nonlinear multicriteria optimization problems, SIAM J Optim, 8, 3, 631-657 (1998) · Zbl 0911.90287 · doi:10.1137/S1052623496307510
[19] De Santis M, Eichfelder G, Niebling J, Rockt S (2019) Solving multiobjective mixed integer convex optimization problems. PreprintSeries of the Institute for Mathematics, Technische Universität Ilmenau, Germany 5:10. http://www.optimization-online.org/DB_HTML/ · Zbl 1453.90139
[20] De Santis, M.; Grani, G.; Palagi, L., Branching with hyperplanes in the criterion space: the frontier partitioner algorithm for biobjective integer programming, Euro J Oper Res, 283, 1, 57-69 (2020) · Zbl 1431.90139 · doi:10.1016/j.ejor.2019.10.034
[21] Eck BJ, Mevissen M (2012) Valve placement in water networks: mixed-integer non-linear optimization with quadratic pipe friction. Report No RC25307 (IRE1209-014), IBM Research
[22] Eck, BJ; Mevissen, M., Quadratic approximations for pipe friction, J Hydroinform, 17, 3, 462 (2015) · doi:10.2166/hydro.2014.170
[23] Ehrgott, M., A discussion of scalarization techniques for multiple objective integer programming, Ann Oper Res, 147, 1, 343-360 (2006) · Zbl 1188.90236 · doi:10.1007/s10479-006-0074-z
[24] Ehrgott, M.; Gandibleux, X., Bound sets for biobjective combinatorial optimization problems, Comput Oper Res, 34, 2674-2694 (2007) · Zbl 1141.90509 · doi:10.1016/j.cor.2005.10.003
[25] Eiger, G.; Shamir, U.; Ben-Tal, A., Optimal design of water distribution networks, Water Resour Res, 30, 9, 2637-2646 (1994) · doi:10.1080/00221689709498644
[26] Fernández, J.; Tóth, B., Obtaining an outer approximation of the efficient set of nonlinear biobjective problems, J Glob Optim, 38, 2, 315-331 (2007) · Zbl 1172.90482 · doi:10.1007/s10898-006-9132-y
[27] Giudicianni, C.; Herrera, M.; di Nardo, A.; Adeyeye, K., Automatic multiscale approach for water networks partitioning into dynamic district metered areas, Water Resour Manag (2020) · doi:10.1007/s11269-019-02471-w
[28] Gleixner, A.; Held, H.; Huang, W.; Vigerske, S., Towards globally optimal operation of water supply networks, Numer Algebra Control Optim, 2, 4, 695-711 (2012) · Zbl 1269.90083 · doi:10.3934/naco.2012.2.695
[29] Gurobi Optimization (2017) Gurobi optimizer reference manual. https://www.gurobi.com/documentation/7.5/refman.pdf. Accessed 6 Feb 2019
[30] Kim, IY; De Weck, OL, Adaptive weighted-sum method for bi-objective optimization: Pareto front generation, Struct Multidiscip Optim, 29, 2, 149-158 (2005) · doi:10.1007/s00158-004-0465-1
[31] Liberti, L.; Pantelides, CC, Convex envelopes of monomials of odd degree, J Glob Optim, 25, 2, 157-168 (2003) · Zbl 1030.90117 · doi:10.1023/A:1021924706467
[32] Logist, F.; Van Impe, J., Novel insights for multi-objective optimisation in engineering using Normal Boundary Intersection and (Enhanced) normalised normal constraint, Struct Multidiscip Optim, 45, 3, 417-431 (2012) · Zbl 1274.90357 · doi:10.1007/s00158-011-0698-8
[33] Mavrotas, G.; Diakoulaki, D., A branch and bound algorithm for mixed zero-one multiple objective linear programming, Eur J Oper Res, 107, 3, 530-541 (1998) · Zbl 0943.90063 · doi:10.1016/S0377-2217(97)00077-5
[34] Mavrotas, G.; Diakoulaki, D., Multi-criteria branch and bound: a vector maximization algorithm for mixed 0-1 multiple objective linear programming, Appl Math Comput, 171, 1, 53-71 (2005) · Zbl 1084.65063 · doi:10.1016/j.amc.2005.01.038
[35] Messac, A.; Ismail-Yahaya, A.; Mattson, CA, The normalized normal constraint method for generating the Pareto frontier, Struct Multidiscip Optim, 25, 2, 86-98 (2003) · Zbl 1243.90200 · doi:10.1007/s00158-002-0276-1
[36] Miettinen, K., Nonlinear multiobjective optimization, Springer, Boston. (1998) · Zbl 0949.90082 · doi:10.1007/978-1-4615-5563-6
[37] Misener R, Floudas CA (2013) GloMIQO: global mixed-integer quadratic optimizer, vol 57. doi:10.1007/s10898-012-9874-7 · Zbl 1272.90034
[38] Nicolini, M.; Zovatto, L., Optimal location and control of pressure reducing valves in water networks, J Water Resour Plan Manag, 135, 3, 178-187 (2009) · doi:10.1061/(ASCE)0733-9496(2009)135:3(178)
[39] Niebling, J.; Eichfelder, G., A branch-and-bound-based algorithm for nonconvex multiobjective optimization, SIAM J Optim, 29, 1, 794-821 (2019) · Zbl 1414.90288 · doi:10.1137/18M1169680
[40] Ofwat (2019) PR19 final determinations: policy summary. https://www.ofwat.gov.uk/wp-content/uploads/2019/12/PR19-final-determinations-Policy-summary.pdf. Accessed 27 Feb 2020
[41] Pecci F (2018) Optimal design for control of water supply networks by mixed integer programming. Ph.D. thesis. Imperial College of Science, Technology and Medicine
[42] 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 (2017) · Zbl 1375.90227 · doi:10.1007/s10589-016-9888-z
[43] Pecci, F.; Abraham, E.; Stoianov, I., Quadratic head loss approximations for optimisation problems in water supply networks, J Hydroinform, 19, 4, 493-506 (2017) · Zbl 1375.90227 · doi:10.2166/hydro.2017.080
[44] Pecci, F.; Abraham, E.; Stoianov, I., Scalable Pareto set generation for multiobjective co-design problems in water distribution networks: a continuous relaxation approach, Struct Multidiscip Optim, 55, 3, 857-869 (2017) · doi:10.1007/s00158-016-1537-8
[45] Pecci, F.; Abraham, E.; Stoianov, I., Global optimality bounds for the placement of control valves in water supply networks, Optim Eng, 67, 1, 201-223 (2018) · Zbl 1375.90227 · doi:10.1007/s10589-016-9888-z
[46] Prasad TD, Tanyimboh TT (2009) Entropy based design of “anytown” water distribution network. Water Distrib Syst Anal 2008 41024(August 2008):1-12. doi:10.1061/41024(340)39
[47] Puranik, Y.; Sahinidis, NV, Domain reduction techniques for global NLP and MINLP optimization, Constraints, 22, 3, 338-376 (2017) · Zbl 1387.90164 · doi:10.1007/s10601-016-9267-5
[48] Sahinidis, NV, Mixed-integer nonlinear programming 2018, Optim Eng, 20, 2, 301-306 (2019) · doi:10.1007/s11081-019-09438-1
[49] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math Program, 103, 2, 225-249 (2005) · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8
[50] Todini, E., Looped water distribution networks design using a resilience index based heuristic approach, Urban Water, 2, 2, 115-122 (2000) · doi:10.1016/S1462-0758(00)00049-2
[51] Ulusoy AJ, Pecci F, Stoianov I (2019) An MINLP-based approach for the design-for-control of resilient water supply systems. IEEE Syst J PP:1-12. doi:10.1109/JSYST.2019.2961104
[52] Van Zyl, JE; Clayton, CRI, The effect of pressure on leakage in water distribution systems, Proc Inst Civ Eng Water Manag, 160, 2, 109-114 (2007) · doi:10.1680/wama.2007.160.2.109
[53] Vigerske, S.; Gleixner, A., SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework, Optim Methods Softw, 33, 3, 563-593 (2018) · Zbl 1398.90112 · doi:10.1080/10556788.2017.1335312
[54] Wachter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math Program, 106, 1, 25-57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
[55] Walters GA, Halhal D, Savic D, Ouazar D (1999) Improved design of “Anytown” distribution network using structured messy genetic algorithms. Urban Water 1(1):23-38. doi:10.1016/s1462-0758(99)00005-9
[56] 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, 12, 9925-9941 (2015) · doi:10.1002/2015WR017466
[57] Xu, C.; Goulter, IC, Reliability-based optimal design of water distribution networks, J Water Resour Plan Manag, 125, 352-362 (1999) · doi:10.1061/(ASCE)0733-9496(1999)125:6(352)
[58] Yu, PL; Zeleny, M., The set of all nondominated solutions in linear cases and a multicriteria simplex method, J Math Anal Appl, 49, 2, 430-468 (1975) · Zbl 0313.65047 · doi:10.1016/0022-247X(75)90189-4
[59] Zamzam, AS; Dall’Anese, E.; Zhao, C.; Taylor, JA; Sidiropoulos, ND, Optimal water-power flow-problem: formulation and distributed optimal solution, IEEE Trans Control Netw Syst, 6, 1, 37-47 (2019) · Zbl 1515.93139 · doi:10.1109/TCNS.2018.2792699
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.