×

On the optimal design of water distribution networks: a practical MINLP approach. (English) Zbl 1293.76045

Summary: We propose a practical solution method for real-world instances of a water-network optimization problem with fixed topology using a nonconvex continuous NLP (NonLinear Programming) relaxation and a MINLP (Mixed Integer NonLinear Programming) search. Our approach employs a relatively simple and accurate model that pays some attention to the requirements of the solvers that we employ. Our view is that in doing so, with the goal of calculating only good feasible solutions, complicated algorithmics can be confined to the MINLP solver. We report successful computational experience using available open-source MINLP software on problems from the literature and on difficult real-world instances. An important contribution of this paper is that the solutions obtained, besides being low cost, are immediately usable in practice because they are characterized by an allocation of diameters to pipes that leads to a correct hydraulic operation of the network. This is not the case for most of the other methods presented in the literature.

MSC:

76B75 Flow control and optimization for incompressible inviscid fluids
76M30 Variational methods applied to problems in fluid mechanics
90C11 Mixed integer programming
90C35 Programming involving graphs or networks
90C90 Applications of mathematical programming

Software:

BARON; minlpBB; CPLEX; AMPL; Bonmin
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Artina S, Walker J (1983) Sull’uso della programmazione a valori misti nel dimensionamento di costo minimo di reti in pressione. Atti Accad Sci Ist Bologna, Serie III, vol 271(X) (in Italian)
[2] Beale E, Tomlin J (1970) Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. In: Lawrence J (ed) Proc of the 5th int conf on operations research, pp 447–454
[3] Bonami P, Lee J (2006) Bonmin users’ manual. Tech rep
[4] Bonami P, Biegler L, Conn A, Cornuéjols G, Grossmann C, Laird I, Lee J, Lodi A, Margot F, Sawaya N, Wächter A (2008) An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optim 5:186–204 · Zbl 1151.90028 · doi:10.1016/j.disopt.2006.10.011
[5] Bonmin (v. 0.1) https://projects.coin-or.org/Bonmin
[6] Bonmin (v. 1.0) https://projects.coin-or.org/Bonmin
[7] Bragalli C, D’Ambrosio C, Lee J, Lodi A, Toth P (2006) An MINLP solution method for a water network problem. In: Azar Y, Erlebach T (eds) Algorithms–ESA 2006. Lecture Notes in Computer Science, vol 4168. Springer, Berlin, pp 696–707 · Zbl 1131.90314
[8] Cunha M, Sousa J (1999) Water distribution network design optimization: simulated annealing approach. J Water Resour Plan Manag, Div Soc Civ Eng 125:215–221 · doi:10.1061/(ASCE)0733-9496(1999)125:4(215)
[9] Dandy G, Simpson A, Murphy L (1996) An improved genetic algorithm for pipe network optimization. Water Resour Res 32:449–458 · doi:10.1029/95WR02917
[10] Eiger G, Shamir U, Ben-Tal A (1994) Optimal design of water distribution networks. Water Resour Res 30:2637–2646 · doi:10.1029/94WR00623
[11] EPANET (v. 2.0) www.epa.gov/ORD/NRMRL/wswrd/epanet.html
[12] Fourer R, Gay D, Kernighan B (2003) AMPL: a modeling language for mathematical programming, 2nd edn. Duxbury Press/Brooks/Cole Publishing Co., N. Scituate · Zbl 0701.90062
[13] Fujiwara O, Khang D (1990) A two-phase decomposition method for optimal design of looped water distribution networks. Water Resour Res 26:539–549 · doi:10.1029/WR026i004p00539
[14] Ilog-Cplex (v. 10.1) www.ilog.com/products/cplex
[15] Ipopt (v. 3.5) https://projects.coin-or.org/Ipopt
[16] Lansey K, Mays L (1989) Optimization model for water distribution system design. J Hydraul Eng 115:1401–1418 · doi:10.1061/(ASCE)0733-9429(1989)115:10(1401)
[17] Leyffer S (April 1998; revised March 1999) User manual for MINLP_BB. Tech rep, University of Dundee
[18] Mathematica (v. 7.0) www.wolfram.com/products/mathematica/index.html
[19] NEOS (v. 5.0) www-neos.mcs.anl.gov/neos
[20] Sahinidis NV, Tawarmalani M (2005) BARON 7.2.5: global optimization of mixed-integer nonlinear programs, User’s Manual
[21] Savic DA, Walters GA (1997) Genetic algorithms for the least-cost design of water distribution networks. J Water Resour Plan Manag 123:67–77 · doi:10.1061/(ASCE)0733-9496(1997)123:2(67)
[22] Schaake JCJ, Lai D (1969) Liner programming and dynamic programming application to water distribution network design. Report 116, Hydrodynamics Laboratory, Department of Civil Engineering, School of Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts
[23] Sherali HD, Subramanian S, Loganathan GV (2001) Effective relaxation and partitioning schemes for solving water distribution network design problems to global optimality. J Glob Optim 19:1–26 · Zbl 0967.90087 · doi:10.1023/A:1008368330827
[24] Tawarmalani M, Sahinidis NV (2004) Global optimization of mixed-integer nonlinear programs: a theoretical and computational study. Math Program 99:563–591 · Zbl 1062.90041 · doi:10.1007/s10107-003-0467-6
[25] Van Den Boomen M, Mazijk AV, Beuken R (2004) First evaluation of new design concepts for self-cleaning distribution networks. J Water Supply, Res Technol, AQUA 53(1):43–50
[26] Walski T (1984) Analysis of water distribution systems. Van Nostrand Reinhold Company, New York
[27] Walski T, Chase D, Savic D (2001) Water distribution modeling. Haestad Methods, Waterbury
[28] Xu C, Goulter I (1999) Reliability-based optimal design of water distribution networks. J Water Resour Plan Manag 125:352–362 · doi:10.1061/(ASCE)0733-9496(1999)125:6(352)
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.