Mathematical programming techniques in water network optimization. (English) Zbl 1346.90211

Eur. J. Oper. Res. 243, No. 3, 774-788 (2015); erratum ibid. 245, No. 1, 338 (2015).
Summary: In this article we survey mathematical programming approaches to problems in the field of drinking water distribution network optimization. Among the predominant topics treated in the literature, we focus on two different, but related problem classes. One can be described by the notion of network design, while the other is more aptly termed by network operation. The basic underlying model in both cases is a nonlinear network flow model, and we give an overview on the more specific modeling aspects in each case. The overall mathematical model is a Mixed Integer Nonlinear Program having a common structure with respect to how water dynamics in pipes are described. Finally, we survey the algorithmic approaches to solve the proposed problems and we discuss computation on various types of water networks.


90B10 Deterministic network models in operations research
90C11 Mixed integer programming
90C27 Combinatorial optimization
90C90 Applications of mathematical programming


SCIP; Bonmin
Full Text: DOI


[1] Abishek, K.; Leyffer, S.; Linderoth, J., Filmint: an outer approximation-based solver for convex mixed-integer nonlinear programs, INFORMS Journal on Computing, 22, 4, 555-567, (2010) · Zbl 1243.90142
[2] Achterberg, T., SCIP: solving constraint integer programs, Mathematical Programming Computation, 1, 1-41, (2009) · Zbl 1171.90476
[3] Babayan, A.; Kapelan, Z.; Savic, D.; Walters, G., Least-cost design of water distribution networks under demand uncertainty, Journal of Water Resources Planning and Management, 131, 5, 375-382, (2005)
[4] Beale, E. M.L.; Tomlin, J. A., Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables, (Lawrence, J., (1970), Tavistock Publications London), 447-454
[5] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numerica, 22, 1-131, (2013) · Zbl 1291.65172
[6] Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tightening techniques for non-convex MINLP, Optimization Methods and Software, 24, 4-5, 597-634, (2009) · Zbl 1179.90237
[7] Berthold, T.; Heinz, S.; Vigerske, S., Extending a CIP framework to solve miqcps, (Lee, J.; Leyffer, S., (2012), Springer New York), 427-444 · Zbl 1242.90120
[8] Bonami, P.; Biegler, L. T.; Conn, A. R.; Cornuéjols, G.; Grossmann, I. E.; Lee, J., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optimization, 5, 2, 186-204, (2008) · Zbl 1151.90028
[9] Bragalli, C.; D’Ambrosio, C.; Lee, J.; Lodi, A.; Toth, P., On the optimal design of water distribution networks: A practical MINLP approach, Optimization and Engineering, 13, 219-246, (2012) · Zbl 1293.76045
[10] Burgschweiger, J.; Gnädig, B.; Steinbach, M. C., Nonlinear programming techniques for operative planning in large drinking water networks, The Open Applied Mathematics Journal, 3, 14-28, (2009) · Zbl 1322.90013
[11] Burgschweiger, J.; Gnädig, B.; Steinbach, M. C., Optimization models for operative planning in drinking water networks, Optimization and Engineering, 10, 343-373, (2009) · Zbl 1273.76072
[12] Coelho, B.; Andrade-Campos, A., Efficiency achievement in water supply systems—A review, Renewable and Sustainable Energy Reviews, 30, 59-84, (2014)
[13] Collins, M.; Cooper, L.; Helgason, R.; Kennington, J.; LeBlanc, L., Solving the pipe network analysis problem using optimization techniques, Management Science, 24, 7, 747-760, (1978) · Zbl 0375.90069
[14] da Conceição Cunha, M.; Ribeiro, L., Tabu search algorithms for water network optimization, European Journal of Operational Research, 157, 3, 746-758, (2004) · Zbl 1067.90013
[15] Dantzig, G., On the significance of solving linear programming problems with some integer variables, Econometrica, 28, 30-44, (1960) · Zbl 0089.16101
[16] De Corte, A.; Sörensen, K., Optimisation of water distribution network design: A critical review, Technical Report 2012-16, (2012), University of Antwerp
[17] Fügenschuh, A.; Humpola, J., A new class of valid inequalities for nonlinear network design problems, Technical Report 13-06, (2013), Zuse-Institut Berlin
[18] Fügenschuh, A.; Humpola, J., A unified view on relaxations for a nonlinear network flow problem, Technical Report 13-31, (2013), Zuse-Institut Berlin
[19] Geißler, B.; Kolb, O.; Lang, J.; Leugering, G.; Martin, A.; Morsi, A., Mixed integer linear models for the optimization of dynamical transport networks, Mathematical Methods of Operations Research, 73, 3, 339-362, (2011) · Zbl 1245.90070
[20] Geißler, B.; Martin, A.; Morsi, A.; Schewe, L., Using piecewise linear functions for solving minlps, (Lee, J.; Leyffer, S., (2012), Springer New York), 287-314 · Zbl 1242.90132
[21] Geißler, B.; Morsi, A.; Schewe, L., A new algorithm for MINLP applied to gas transport energy cost minimization, (Jünger, M.; Reinelt, G., (2013), Springer Berlin/Heidelberg), 321-353 · Zbl 1317.90209
[22] Ghaddar, B.; Naoum-Sawaya, J.; Kishimoto, A.; Taheri, N.; Eck, B., A Lagrangian decomposition approach for the pump scheduling problem in water networks, European Journal of Operational Research, 241, 490-501, (2015) · Zbl 1339.90135
[23] Ghidaoui, M. S.; Zhao, M.; McInnis, D. A.; Axworthy, D. H., A review of water hammer theory and practice, Applied Mechanics Reviews, 58, 49-76, (2005)
[24] Gleixner, A. M., Private communication, (2013)
[25] Gleixner, A. M.; Held, H.; Huang, W.; Vigerske, S., Towards globally optimal operation of water supply networks, Numerical Algebra, Control and Optimization, 2, 695-711, (2012) · Zbl 1269.90083
[26] Huang, C.; Chang, C.; Ling, H., A mathematical programming model for water usage and treatment network design, Industrial Engineering and Chemical Research, 38, 7, 2666-2679, (1999)
[27] Kolb, O.; Lang, J., Simulation and continuous optimization, (Martin, A.; Klamroth, K.; Lang, J.; Leugering, G.; Morsi, A.; Oberlack, M.; Ostrowski, M., (2012), Springer Basel), 17-33 · Zbl 1256.65064
[28] Kolb, O.; Morsi, A.; Lang, J.; Martin, A., Nonlinear and mixed integer linear programming, (Martin, A.; Klamroth, K.; Lang, J.; Leugering, G.; Morsi, A.; Oberlack, M.; Ostrowski, M., (2012), Springer Basel), 55-65 · Zbl 1259.90137
[29] Laird, C. D.; Biegler, L. T.; Van Bloemen Waanders, B. G., Real-time, large-scale optimization of water network systems using a subdomain approach, (Biegler, L. T.; Ghattas, O.; Heinkenschloss, M.; Keyes, D.; Van Bloemen Waanders, B. G., (2007), SIAM Philadelphia) · Zbl 1227.90009
[30] Lorenz, C. L.; Laird, C. D.; Biegler, L. T.; Van Bloemen Waanders, B. G., A mixed integer approach for obtaining unique solutions in source inversion of drinking water networks, Journal of Water Resources Planning and Management, 132, 242-251, (2006)
[31] Markowitz, H.; Manne, A., On the solution of discrete programming problems, Econometrica, 25, 84-110, (1957) · Zbl 0078.34005
[32] Morsi, A., Solving MINLPs on loosely-coupled networks with applications in water and gas network optimization, (2013), Friedrich-Alexander-Universität Erlangen-Nürnberg
[33] Morsi, A.; Geißler, B.; Martin, A., Mixed integer optimization of water supply networks, (Martin, A.; Klamroth, K.; Lang, J.; Leugering, G.; Morsi, A.; Oberlack, M.; Ostrowski, M., (2012), Springer Basel), 35-54 · Zbl 1259.90076
[34] Pilati, S. and Todini, E. ( n.d.). La verifica delle reti idrauliche in pressione (the verification of hydraulic networks under pressure). Unpublished data (in italian).
[35] Raghunathan, A. U., Global optimization of nonlinear network design, SIAM Journal on Optimization, 23, 1, 268-295, (2013) · Zbl 1270.90036
[36] Rauch, W.; Harremoës, P., Genetic algorithms in real time control applied to minimize transient pollution from urban wastewater systems, Water Research, 33, 5, 1265-1277, (1999)
[37] Rossman, L. A.; Boulos, P. F., Numerical methods for modeling water quality in distribution systems: A comparison, Journal of Water Resources Planning and Management, 122, 137-146, (1996)
[38] Rovatti, R.; D’Ambrosio, C.; Lodi, A.; Martello, S., Optimistic MILP modeling of non-linear optimization problems, European Journal of Operational Research, 239, 1, 32-45, (2014) · Zbl 1339.90250
[39] Tawarmalani, M.; Sahinidis, N. V., A polyhedral branch-and-cut approach to global optimization, Mathematical Programming, 103, 2, 225-249, (2005) · Zbl 1099.90047
[40] Verleye, D.; Aghezzaf, E.-H., Optimising production and distribution operations in large water supply networks: A piecewise linear optimisation approach, International Journal of Production Research, 51, 23-24, 7170-7189, (2013)
[41] Vielma, J.; Nemhauser, G., Modeling disjunctive constraints with a logarithmic number of binary variables and constraints, Mathematical Programming, 128, 1-2, 49-72, (2011) · Zbl 1218.90137
[42] Vigerske, S., Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming, (2012), Humboldt-Universität zu Berlin, Ph.D. thesis
[43] Vigerske, S. ( 2012b). Solving MINLPs with SCIP. In Conference talk, 21st international symposium on mathematical programming, 19th-24th August. Berlin, Germany.
[44] Vigerske, S., Private communication, (2013)
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.