Towards globally optimal operation of water supply networks

Previous Article
Two-stage stochastic programs: Integer variables, dominance relations and PDE constraints
NACO Home
This Issue
Next Article
The integrated size and price optimization problem

2012, 2(4): 695-711. doi: 10.3934/naco.2012.2.695

Towards globally optimal operation of water supply networks

Ambros M. Gleixner ^1, , Harald Held ^2, , Wei Huang ^3, and Stefan Vigerske ^4,

1.	Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany
2.	Siemens AG, Corporate Technology (CT RTC AUC SIM-DE), Otto-Hahn-Ring 6, 81739 Munich, Germany
3.	Technische Universität München, International School of Applied Mathematics, Boltzmannstr. 3, 85748 Garching b. Munich, Germany
4.	Humboldt-Universität, Department of Mathematics, Unter den Linden 6, 10099 Berlin, Germany

Received March 2012 Revised October 2012 Published November 2012

Abstract
Related Papers

This paper is concerned with optimal operation of pressurized water supply networks at a fixed point in time. We use a mixed-integer nonlinear programming (MINLP) model incorporating both the nonlinear physical laws and the discrete decisions such as switching pumps on and off. We demonstrate that for instances from our industry partner, these stationary models can be solved to $\epsilon$-global optimality within small running times using problem-specific presolving and state-of-the-art MINLP algorithms.
In our modeling, we emphasize the importance of distinguishing between what we call real and imaginary flow, i.e., taking into account that the law of Darcy-Weisbach correlates pressure difference and flow along a pipe if and only if water is available at the high pressure end of a pipe. Our modeling solution extends to the dynamic operative planning problem.

Keywords: water supply networks., operative planning, global optimization, Nonconvex MINLP.

Mathematics Subject Classification: Primary: 90C26; Secondary: 90C11, 90C9.

Citation: Ambros M. Gleixner, Harald Held, Wei Huang, Stefan Vigerske. Towards globally optimal operation of water supply networks. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 695-711. doi: 10.3934/naco.2012.2.695

References:

[1]	Tobias Achterberg, "Constraint Integer Programming," PhD thesis, Technische Universität Berlin, 2007.
[2]	Tobias Achterberg, SCIP: Solving constraint integer programs, Mathematical Programming Computation, 1 (2009), 1-41, doi: 10.1007/s12532-008-0001-1.
[3]	Pietro Belotti, Jon Lee, Leo Liberti, Francois Margot and Andreas Wächter, Branching and bounds tightening techniques for non-convex MINLP, Optimization Methods and Software, 24 (2009), 597-634. doi: 10.1080/10556780903087124.
[4]	Timo Berthold, "Primal Heuristics for Mixed Integer Programs," Master's thesis, Technische Universität Berlin, 2006.
[5]	Timo Berthold and Ambros M. Gleixner, Undercover - a primal heuristic for MINLP based on sub-MIPs generated by set covering, in "Proceedings of the EWMINLP" (eds. Pierre Bonami, Leo Liberti, Andrew J. Miller and Annick Sartenaer), (2010), 103-112.
[6]	Timo Berthold and Ambros M. Gleixner, Undercover - a primal MINLP heuristic exploring a largest sub-MIP, ZIB-Report 12-07 (2012), Zuse Institute Berlin, http://vs24.kobv.de/opus4-zib/frontdoor/index/index/docId/1463/.
[7]	Timo Berthold, Stefan Heinz, Marc E. Pfetsch and Stefan Vigerske, Large neighborhood search beyond MIP, in "Proceedings of the 9th Metaheuristics International Conference" (eds. Luca Di Gaspero, Andrea Schaerf, and Thomas Stützle), (2011), 51-60.
[8]	Timo Berthold, Stefan Heinz and Stefan Vigerske, Extending a CIP framework to solve MIQCPs, in "The IMA volumes in Mathematics and its Applications" (eds. Jon Lee and Sven Leyffer), 154 (2012), 427-444. doi: 10.1007/978-1-4614-1927-3_15.
[9]	Cristiana Bragalli, Claudia D'mbrosio, Jon Lee, Andrea Lodi and Paolo Toth, On the optimal design of water distribution networks: a practical MINLP approach, Optimization and Engineering, 13 (2012), 219-246. doi: 10.1007/s11081-011-9141-7.
[10]	Jens Burgschweiger, Bernd Gnädig and Marc C. Steinbach, Optimization models for operative planning in drinking water networks, ZIB-Report 04-48 (2004), Zuse Institute Berlin, http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/823.
[11]	Björn Geißler, Oliver Kolb, Jens Lang, Günter Leugering, Alexander Martin and Antonio Morsi, Mixed integer linear models for the optimization of dynamical transport networks, Mathematical Methods of Operations Research, 73 (2011), 339-362, doi: 10.1007/s00186-011-0354-5.
[12]	Wei Huang, "Operative Planning of Water Supply Networks by Mixed Integer Nonlinear Programming," Master's thesis, Freie Universität Berlin, 2011.
[13]	Kathrin Klamroth, Jens Lang, Günter Leugering, Alexander Martin, Antonio Morsi, Martin Oberlack, Manfred Ostrowski and Roland Rosen, "Mathematical Optimization of Water Networks," International Series of Numerical Mathematics, 162 (2012), Birkhäuser-Science, Basel.
[14]	Oliver Kolb, "Simulation and Optimization of Gas and Water Supply Networks," PhD thesis, Technische Universität Darmstadt, 2011.
[15]	Ailsa H. Land and Alison G. Doig, An automatic method for solving discrete programming problems, Econometrica, 28 (1960), 497-520.
[16]	Youdong Lin and Linus Schrage, The global solver in the LINDO API, Optimization Methods & Software, 24 (2009), 657-668. doi: 10.1080/10556780902753221.
[17]	Hanif D. Sherali and Ernest P. Smith, A global optimization approach to a water distribution network design problem, Journal of Global Optimization, 11 (1997), 107-132. doi: 10.1023/A:1008207817095.
[18]	Mohit Tawarmalani and Nikolaos V. Sahinidis, Global optimization of mixed-integer nonlinear programs: A theoretical and computational study, Mathematical Programming, Ser. A, 99 (2004), 563-591. doi: 10.1007/s10107-003-0467-6.
[19]	Stefan Vigerske, "Decomposition of Multistage Stochastic Programs and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming," Ph.D thesis, Humboldt-Universität zu Berlin, 2012.
[20]	Andreas Wächter and Lorenz T. Biegler, On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Mathematical Programming, Ser. A, 106 (2006), 125-157. doi: 10.1007/s10107-004-0559-y.
[21]	CppAD, "A Package for Differentiation of C++ algorithms," Available from: http://www.coin-or.org/CppAD/.
[22]	EPANET, "A software that models water distribution piping systems," Available from: http://www.epa.gov/nrmrl/wswrd/dw/epanet.html.
[23]	Ipopt, "Interior Point Optimizer," Available from: http://www.coin-or.org/Ipopt/.
[24]	SCIP, "Solving Constraint Integer Programs," Available from: http://scip.zib.de/.
[25]	SoPlex, "Sequential Object-oriented SimPlex," Available from: http://soplex.zib.de/.
[26]	Zimpl, "Zuse Institute Mathematical Programming Language," Available from: http://zimpl.zib.de/.

show all references

References:

[1]	Tobias Achterberg, "Constraint Integer Programming," PhD thesis, Technische Universität Berlin, 2007.
[2]	Tobias Achterberg, SCIP: Solving constraint integer programs, Mathematical Programming Computation, 1 (2009), 1-41, doi: 10.1007/s12532-008-0001-1.
[3]	Pietro Belotti, Jon Lee, Leo Liberti, Francois Margot and Andreas Wächter, Branching and bounds tightening techniques for non-convex MINLP, Optimization Methods and Software, 24 (2009), 597-634. doi: 10.1080/10556780903087124.
[4]	Timo Berthold, "Primal Heuristics for Mixed Integer Programs," Master's thesis, Technische Universität Berlin, 2006.
[5]	Timo Berthold and Ambros M. Gleixner, Undercover - a primal heuristic for MINLP based on sub-MIPs generated by set covering, in "Proceedings of the EWMINLP" (eds. Pierre Bonami, Leo Liberti, Andrew J. Miller and Annick Sartenaer), (2010), 103-112.
[6]	Timo Berthold and Ambros M. Gleixner, Undercover - a primal MINLP heuristic exploring a largest sub-MIP, ZIB-Report 12-07 (2012), Zuse Institute Berlin, http://vs24.kobv.de/opus4-zib/frontdoor/index/index/docId/1463/.
[7]	Timo Berthold, Stefan Heinz, Marc E. Pfetsch and Stefan Vigerske, Large neighborhood search beyond MIP, in "Proceedings of the 9th Metaheuristics International Conference" (eds. Luca Di Gaspero, Andrea Schaerf, and Thomas Stützle), (2011), 51-60.
[8]	Timo Berthold, Stefan Heinz and Stefan Vigerske, Extending a CIP framework to solve MIQCPs, in "The IMA volumes in Mathematics and its Applications" (eds. Jon Lee and Sven Leyffer), 154 (2012), 427-444. doi: 10.1007/978-1-4614-1927-3_15.
[9]	Cristiana Bragalli, Claudia D'mbrosio, Jon Lee, Andrea Lodi and Paolo Toth, On the optimal design of water distribution networks: a practical MINLP approach, Optimization and Engineering, 13 (2012), 219-246. doi: 10.1007/s11081-011-9141-7.
[10]	Jens Burgschweiger, Bernd Gnädig and Marc C. Steinbach, Optimization models for operative planning in drinking water networks, ZIB-Report 04-48 (2004), Zuse Institute Berlin, http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/823.
[11]	Björn Geißler, Oliver Kolb, Jens Lang, Günter Leugering, Alexander Martin and Antonio Morsi, Mixed integer linear models for the optimization of dynamical transport networks, Mathematical Methods of Operations Research, 73 (2011), 339-362, doi: 10.1007/s00186-011-0354-5.
[12]	Wei Huang, "Operative Planning of Water Supply Networks by Mixed Integer Nonlinear Programming," Master's thesis, Freie Universität Berlin, 2011.
[13]	Kathrin Klamroth, Jens Lang, Günter Leugering, Alexander Martin, Antonio Morsi, Martin Oberlack, Manfred Ostrowski and Roland Rosen, "Mathematical Optimization of Water Networks," International Series of Numerical Mathematics, 162 (2012), Birkhäuser-Science, Basel.
[14]	Oliver Kolb, "Simulation and Optimization of Gas and Water Supply Networks," PhD thesis, Technische Universität Darmstadt, 2011.
[15]	Ailsa H. Land and Alison G. Doig, An automatic method for solving discrete programming problems, Econometrica, 28 (1960), 497-520.
[16]	Youdong Lin and Linus Schrage, The global solver in the LINDO API, Optimization Methods & Software, 24 (2009), 657-668. doi: 10.1080/10556780902753221.
[17]	Hanif D. Sherali and Ernest P. Smith, A global optimization approach to a water distribution network design problem, Journal of Global Optimization, 11 (1997), 107-132. doi: 10.1023/A:1008207817095.
[18]	Mohit Tawarmalani and Nikolaos V. Sahinidis, Global optimization of mixed-integer nonlinear programs: A theoretical and computational study, Mathematical Programming, Ser. A, 99 (2004), 563-591. doi: 10.1007/s10107-003-0467-6.
[19]	Stefan Vigerske, "Decomposition of Multistage Stochastic Programs and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming," Ph.D thesis, Humboldt-Universität zu Berlin, 2012.
[20]	Andreas Wächter and Lorenz T. Biegler, On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Mathematical Programming, Ser. A, 106 (2006), 125-157. doi: 10.1007/s10107-004-0559-y.
[21]	CppAD, "A Package for Differentiation of C++ algorithms," Available from: http://www.coin-or.org/CppAD/.
[22]	EPANET, "A software that models water distribution piping systems," Available from: http://www.epa.gov/nrmrl/wswrd/dw/epanet.html.
[23]	Ipopt, "Interior Point Optimizer," Available from: http://www.coin-or.org/Ipopt/.
[24]	SCIP, "Solving Constraint Integer Programs," Available from: http://scip.zib.de/.
[25]	SoPlex, "Sequential Object-oriented SimPlex," Available from: http://soplex.zib.de/.
[26]	Zimpl, "Zuse Institute Mathematical Programming Language," Available from: http://zimpl.zib.de/.

[1]	Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial and Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157
[2]	Juan Carlos López Alfonso, Giuseppe Buttazzo, Bosco García-Archilla, Miguel A. Herrero, Luis Núñez. A class of optimization problems in radiotherapy dosimetry planning. Discrete and Continuous Dynamical Systems - B, 2012, 17 (6) : 1651-1672. doi: 10.3934/dcdsb.2012.17.1651
[3]	Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete and Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212
[4]	Radu C. Cascaval, Ciro D'Apice, Maria Pia D'Arienzo, Rosanna Manzo. Flow optimization in vascular networks. Mathematical Biosciences & Engineering, 2017, 14 (3) : 607-624. doi: 10.3934/mbe.2017035
[5]	Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1943-1971. doi: 10.3934/jimo.2020053
[6]	Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial and Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117
[7]	Chunrong Chen. A unified nonlinear augmented Lagrangian approach for nonconvex vector optimization. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 495-508. doi: 10.3934/naco.2011.1.495
[8]	Weijun Zhou, Youhua Zhou. On the strong convergence of a modified Hestenes-Stiefel method for nonconvex optimization. Journal of Industrial and Management Optimization, 2013, 9 (4) : 893-899. doi: 10.3934/jimo.2013.9.893
[9]	Qilin Wang, S. J. Li. Higher-order sensitivity analysis in nonconvex vector optimization. Journal of Industrial and Management Optimization, 2010, 6 (2) : 381-392. doi: 10.3934/jimo.2010.6.381
[10]	Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial and Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135
[11]	Qiong Liu, Jialiang Liu, Zhaorui Dong, Mengmeng Zhan, Zhen Mei, Baosheng Ying, Xinyu Shao. Integrated optimization of process planning and scheduling for reducing carbon emissions. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1025-1055. doi: 10.3934/jimo.2020010
[12]	Hanyu Gu, Hue Chi Lam, Yakov Zinder. Planning rolling stock maintenance: Optimization of train arrival dates at a maintenance center. Journal of Industrial and Management Optimization, 2022, 18 (2) : 747-772. doi: 10.3934/jimo.2020177
[13]	Giuseppe Buttazzo, Filippo Santambrogio. Asymptotical compliance optimization for connected networks. Networks and Heterogeneous Media, 2007, 2 (4) : 761-777. doi: 10.3934/nhm.2007.2.761
[14]	Michael Herty, Veronika Sachers. Adjoint calculus for optimization of gas networks. Networks and Heterogeneous Media, 2007, 2 (4) : 733-750. doi: 10.3934/nhm.2007.2.733
[15]	Yuki Kumagai. Social networks and global transactions. Journal of Dynamics and Games, 2019, 6 (3) : 211-219. doi: 10.3934/jdg.2019015
[16]	Joseph Geunes, Panos M. Pardalos. Introduction to the Special Issue on Supply Chain Optimization. Journal of Industrial and Management Optimization, 2007, 3 (1) : i-ii. doi: 10.3934/jimo.2007.3.1i
[17]	Gonglin Yuan, Zhan Wang, Pengyuan Li. Global convergence of a modified Broyden family method for nonconvex functions. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021164
[18]	Yi Jing, Wenchuan Li. Integrated recycling-integrated production - distribution planning for decentralized closed-loop supply chain. Journal of Industrial and Management Optimization, 2018, 14 (2) : 511-539. doi: 10.3934/jimo.2017058
[19]	Pierre Fabrie, Elodie Jaumouillé, Iraj Mortazavi, Olivier Piller. Numerical approximation of an optimization problem to reduce leakage in water distribution systems. Mathematical Control and Related Fields, 2012, 2 (2) : 101-120. doi: 10.3934/mcrf.2012.2.101
[20]	Ö. Uğur, G. W. Weber. Optimization and dynamics of gene-environment networks with intervals. Journal of Industrial and Management Optimization, 2007, 3 (2) : 357-379. doi: 10.3934/jimo.2007.3.357

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Ambros M. Gleixner Harald Held Wei Huang Stefan Vigerske
on Google Scholar
Ambros M. Gleixner Harald Held Wei Huang Stefan Vigerske

[Back to Top]