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]

Bernold Fiedler. Global Hopf bifurcation in networks with fast feedback cycles. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 177-203. doi: 10.3934/dcdss.2020344

[2]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117

[3]

D. R. Michiel Renger, Johannes Zimmer. Orthogonality of fluxes in general nonlinear reaction networks. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 205-217. doi: 10.3934/dcdss.2020346

[4]

Hongguang Ma, Xiang Li. Multi-period hazardous waste collection planning with consideration of risk stability. Journal of Industrial & Management Optimization, 2021, 17 (1) : 393-408. doi: 10.3934/jimo.2019117

[5]

Sushil Kumar Dey, Bibhas C. Giri. Coordination of a sustainable reverse supply chain with revenue sharing contract. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020165

[6]

Zonghong Cao, Jie Min. Selection and impact of decision mode of encroachment and retail service in a dual-channel supply chain. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020167

[7]

Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082

[8]

Jianhua Huang, Yanbin Tang, Ming Wang. Singular support of the global attractor for a damped BBM equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020345

[9]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[10]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005

[11]

Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098

[12]

Cheng He, Changzheng Qu. Global weak solutions for the two-component Novikov equation. Electronic Research Archive, 2020, 28 (4) : 1545-1562. doi: 10.3934/era.2020081

[13]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055

[14]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[15]

Yi An, Bo Li, Lei Wang, Chao Zhang, Xiaoli Zhou. Calibration of a 3D laser rangefinder and a camera based on optimization solution. Journal of Industrial & Management Optimization, 2021, 17 (1) : 427-445. doi: 10.3934/jimo.2019119

[16]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100

[17]

Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial & Management Optimization, 2021, 17 (1) : 233-259. doi: 10.3934/jimo.2019109

[18]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102

[19]

Ahmad Z. Fino, Wenhui Chen. A global existence result for two-dimensional semilinear strongly damped wave equation with mixed nonlinearity in an exterior domain. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5387-5411. doi: 10.3934/cpaa.2020243

[20]

Mengni Li. Global regularity for a class of Monge-Ampère type equations with nonzero boundary conditions. Communications on Pure & Applied Analysis, 2021, 20 (1) : 301-317. doi: 10.3934/cpaa.2020267

 Impact Factor: 

Metrics

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

[Back to Top]