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

Towards globally optimal operation of water supply networks

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

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.
Citation: Ambros M. Gleixner, Harald Held, Wei Huang, Stefan Vigerske. Towards globally optimal operation of water supply networks. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 695-711. doi: 10.3934/naco.2012.2.695
References:
[1]

Tobias Achterberg, "Constraint Integer Programming,", PhD thesis, (2007).   Google Scholar

[2]

Tobias Achterberg, SCIP: Solving constraint integer programs,, Mathematical Programming Computation, 1 (2009), 1.  doi: 10.1007/s12532-008-0001-1.  Google Scholar

[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.  doi: 10.1080/10556780903087124.  Google Scholar

[4]

Timo Berthold, "Primal Heuristics for Mixed Integer Programs,", Master's thesis, (2006).   Google Scholar

[5]

Timo Berthold and Ambros M. Gleixner, Undercover - a primal heuristic for MINLP based on sub-MIPs generated by set covering,, in, (2010), 103.   Google Scholar

[6]

Timo Berthold and Ambros M. Gleixner, Undercover - a primal MINLP heuristic exploring a largest sub-MIP,, ZIB-Report 12-07 (2012), (2012), 12.   Google Scholar

[7]

Timo Berthold, Stefan Heinz, Marc E. Pfetsch and Stefan Vigerske, Large neighborhood search beyond MIP,, in, (2011), 51.   Google Scholar

[8]

Timo Berthold, Stefan Heinz and Stefan Vigerske, Extending a CIP framework to solve MIQCPs,, in, 154 (2012), 427.  doi: 10.1007/978-1-4614-1927-3_15.  Google Scholar

[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.  doi: 10.1007/s11081-011-9141-7.  Google Scholar

[10]

Jens Burgschweiger, Bernd Gnädig and Marc C. Steinbach, Optimization models for operative planning in drinking water networks,, ZIB-Report 04-48 (2004), (2004), 04.   Google Scholar

[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.  doi: 10.1007/s00186-011-0354-5.  Google Scholar

[12]

Wei Huang, "Operative Planning of Water Supply Networks by Mixed Integer Nonlinear Programming,", Master's thesis, (2011).   Google Scholar

[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).   Google Scholar

[14]

Oliver Kolb, "Simulation and Optimization of Gas and Water Supply Networks,", PhD thesis, (2011).   Google Scholar

[15]

Ailsa H. Land and Alison G. Doig, An automatic method for solving discrete programming problems,, Econometrica, 28 (1960), 497.   Google Scholar

[16]

Youdong Lin and Linus Schrage, The global solver in the LINDO API,, Optimization Methods & Software, 24 (2009), 657.  doi: 10.1080/10556780902753221.  Google Scholar

[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.  doi: 10.1023/A:1008207817095.  Google Scholar

[18]

Mohit Tawarmalani and Nikolaos V. Sahinidis, Global optimization of mixed-integer nonlinear programs: A theoretical and computational study,, Mathematical Programming, 99 (2004), 563.  doi: 10.1007/s10107-003-0467-6.  Google Scholar

[19]

Stefan Vigerske, "Decomposition of Multistage Stochastic Programs and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming,", Ph.D thesis, (2012).   Google Scholar

[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, 106 (2006), 125.  doi: 10.1007/s10107-004-0559-y.  Google Scholar

[21]

CppAD, "A Package for Differentiation of C++ algorithms,", Available from: , ().   Google Scholar

[22]

EPANET, "A software that models water distribution piping systems,", Available from: , ().   Google Scholar

[23]

Ipopt, "Interior Point Optimizer,", Available from: , ().   Google Scholar

[24]

SCIP, "Solving Constraint Integer Programs,", Available from: , ().   Google Scholar

[25]

SoPlex, "Sequential Object-oriented SimPlex,", Available from: , ().   Google Scholar

[26]

Zimpl, "Zuse Institute Mathematical Programming Language,", Available from: , ().   Google Scholar

show all references

References:
[1]

Tobias Achterberg, "Constraint Integer Programming,", PhD thesis, (2007).   Google Scholar

[2]

Tobias Achterberg, SCIP: Solving constraint integer programs,, Mathematical Programming Computation, 1 (2009), 1.  doi: 10.1007/s12532-008-0001-1.  Google Scholar

[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.  doi: 10.1080/10556780903087124.  Google Scholar

[4]

Timo Berthold, "Primal Heuristics for Mixed Integer Programs,", Master's thesis, (2006).   Google Scholar

[5]

Timo Berthold and Ambros M. Gleixner, Undercover - a primal heuristic for MINLP based on sub-MIPs generated by set covering,, in, (2010), 103.   Google Scholar

[6]

Timo Berthold and Ambros M. Gleixner, Undercover - a primal MINLP heuristic exploring a largest sub-MIP,, ZIB-Report 12-07 (2012), (2012), 12.   Google Scholar

[7]

Timo Berthold, Stefan Heinz, Marc E. Pfetsch and Stefan Vigerske, Large neighborhood search beyond MIP,, in, (2011), 51.   Google Scholar

[8]

Timo Berthold, Stefan Heinz and Stefan Vigerske, Extending a CIP framework to solve MIQCPs,, in, 154 (2012), 427.  doi: 10.1007/978-1-4614-1927-3_15.  Google Scholar

[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.  doi: 10.1007/s11081-011-9141-7.  Google Scholar

[10]

Jens Burgschweiger, Bernd Gnädig and Marc C. Steinbach, Optimization models for operative planning in drinking water networks,, ZIB-Report 04-48 (2004), (2004), 04.   Google Scholar

[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.  doi: 10.1007/s00186-011-0354-5.  Google Scholar

[12]

Wei Huang, "Operative Planning of Water Supply Networks by Mixed Integer Nonlinear Programming,", Master's thesis, (2011).   Google Scholar

[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).   Google Scholar

[14]

Oliver Kolb, "Simulation and Optimization of Gas and Water Supply Networks,", PhD thesis, (2011).   Google Scholar

[15]

Ailsa H. Land and Alison G. Doig, An automatic method for solving discrete programming problems,, Econometrica, 28 (1960), 497.   Google Scholar

[16]

Youdong Lin and Linus Schrage, The global solver in the LINDO API,, Optimization Methods & Software, 24 (2009), 657.  doi: 10.1080/10556780902753221.  Google Scholar

[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.  doi: 10.1023/A:1008207817095.  Google Scholar

[18]

Mohit Tawarmalani and Nikolaos V. Sahinidis, Global optimization of mixed-integer nonlinear programs: A theoretical and computational study,, Mathematical Programming, 99 (2004), 563.  doi: 10.1007/s10107-003-0467-6.  Google Scholar

[19]

Stefan Vigerske, "Decomposition of Multistage Stochastic Programs and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming,", Ph.D thesis, (2012).   Google Scholar

[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, 106 (2006), 125.  doi: 10.1007/s10107-004-0559-y.  Google Scholar

[21]

CppAD, "A Package for Differentiation of C++ algorithms,", Available from: , ().   Google Scholar

[22]

EPANET, "A software that models water distribution piping systems,", Available from: , ().   Google Scholar

[23]

Ipopt, "Interior Point Optimizer,", Available from: , ().   Google Scholar

[24]

SCIP, "Solving Constraint Integer Programs,", Available from: , ().   Google Scholar

[25]

SoPlex, "Sequential Object-oriented SimPlex,", Available from: , ().   Google Scholar

[26]

Zimpl, "Zuse Institute Mathematical Programming Language,", Available from: , ().   Google Scholar

[1]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212

[2]

Ying Yang. Global classical solutions to two-dimensional chemotaxis-shallow water system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2625-2643. doi: 10.3934/dcdsb.2020198

[3]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023

[4]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028

[5]

Juan Manuel Pastor, Javier García-Algarra, José M. Iriondo, José J. Ramasco, Javier Galeano. Dragging in mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 37-52. doi: 10.3934/nhm.2015.10.37

[6]

Gheorghe Craciun, Jiaxin Jin, Polly Y. Yu. Single-target networks. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021065

[7]

Juliang Zhang, Jian Chen. Information sharing in a make-to-stock supply chain. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1169-1189. doi: 10.3934/jimo.2014.10.1169

[8]

Madalina Petcu, Roger Temam. The one dimensional shallow water equations with Dirichlet boundary conditions on the velocity. Discrete & Continuous Dynamical Systems - S, 2011, 4 (1) : 209-222. doi: 10.3934/dcdss.2011.4.209

[9]

Alessandro Gondolo, Fernando Guevara Vasquez. Characterization and synthesis of Rayleigh damped elastodynamic networks. Networks & Heterogeneous Media, 2014, 9 (2) : 299-314. doi: 10.3934/nhm.2014.9.299

[10]

Juan Manuel Pastor, Javier García-Algarra, Javier Galeano, José María Iriondo, José J. Ramasco. A simple and bounded model of population dynamics for mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 53-70. doi: 10.3934/nhm.2015.10.53

[11]

Min Li, Jiahua Zhang, Yifan Xu, Wei Wang. Effects of disruption risk on a supply chain with a risk-averse retailer. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021024

[12]

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094

[13]

Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021008

[14]

José Raúl Quintero, Juan Carlos Muñoz Grajales. On the existence and computation of periodic travelling waves for a 2D water wave model. Communications on Pure & Applied Analysis, 2018, 17 (2) : 557-578. doi: 10.3934/cpaa.2018030

[15]

Carlos Gutierrez, Nguyen Van Chau. A remark on an eigenvalue condition for the global injectivity of differentiable maps of $R^2$. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 397-402. doi: 10.3934/dcds.2007.17.397

[16]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[17]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617

[18]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[19]

Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206

[20]

Benrong Zheng, Xianpei Hong. Effects of take-back legislation on pricing and coordination in a closed-loop supply chain. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021035

 Impact Factor: 

Metrics

  • PDF downloads (76)
  • HTML views (0)
  • Cited by (12)

[Back to Top]