Polynomial optimization for water networks: global solutions for the valve setting problem.

*(English)*Zbl 1403.90200Summary: This paper explores polynomial optimization techniques for two formulations of the energy conservation constraint for the valve setting problem in water networks. The sparse hierarchy of semidefinite programing relaxations is used to derive globally optimal bounds for an existing cubic and a new quadratic problem formulation. Both formulations use an approximation for friction loss that has an accuracy consistent with the experimental error of the classical equations. Solutions using the proposed approach are reported on four water networks ranging in size from 4 to 2000 nodes and are compared against a local solver, Ipopt and a global solver, Couenne. Computational results found global solutions using both formulations with the quadratic formulation having better time efficiency due to the reduced degree of the polynomial optimization problem and the sparsity of the constraint matrix. The approaches presented in this paper may also allow global solutions to other water network steady-state optimization problems formulated with continuous variables.

##### MSC:

90B10 | Deterministic network models in operations research |

90C22 | Semidefinite programming |

90C35 | Programming involving graphs or networks |

90C90 | Applications of mathematical programming |

##### Keywords:

global optimization; polynomial optimization; semidefinite programing; valve setting problem; water networks
PDF
BibTeX
XML
Cite

\textit{B. Ghaddar} et al., Eur. J. Oper. Res. 261, No. 2, 450--459 (2017; Zbl 1403.90200)

Full Text:
DOI

##### References:

[1] | Alonso, J. M.; Alvarruiz, F.; Guerrero, D.; Hernández, V.; Ruiz, P. A.; Vidal, A. M., Parallel computing in water network analysis and leakage minimization, Journal of Water Resources Planning and Management, 126, 4, 251-260, (2000) |

[2] | Association, A. W.W., Steel pipe: A guide for design and installation, 11, (1989), AWWA |

[3] | Berghout, B. L.; Kuczera, G., Network linear programming as pipe network hydraulic analysis tool, Journal of Hydraulic Engineering, 123, 6, 549-559, (1997) |

[4] | 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, 2, 219-246, (2012) · Zbl 1293.76045 |

[5] | Couenne (2011). (v. 0.4). https://projects.coin-or.org/Couenne (Accessed 16.12.15). |

[6] | D’Ambrosio, C.; Lodi, A.; Wiese, S.; Bragalli, C., Mathematical programming techniques in water network optimization, European Journal of Operational Research, 243, 3, 774-788, (2015) · Zbl 1346.90211 |

[7] | Eck, B. J.; Mevissen, M., Fast non-linear optimization for design problems on water networks, Proceedings of the 2013 world environmental and water resources congress, (2013) |

[8] | Eck, B. J.; Mevissen, M., Quadratic approximations for pipe friction, Journal of Hydro Informatics, 17, 3, 462-472, (2015) |

[9] | Farmani, R.; Savic, D.; Walters, G., EXNET benchmark problem for multi-objective optimization of large water systems, Proceedings of the IFAC workshop onmodelling and control for participatory planning and managing water systems, (2004), Italy |

[10] | Fujisawa, K.; Nakata, K.; Yamashita, M.; Fukuda, M., SDPA project: solving large-scale semidefinite programs, Journal of Operations Research Society of Japan, 50, 278-298, (2007) · Zbl 1142.90465 |

[11] | Germanopoulos, G.; Jowitt, P., Leakage reduction by excess pressure minimization in a water supply network, ICE Proceedings, 87, 195-214, (1989) |

[12] | 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, 2, 490-501, (2015) · Zbl 1339.90135 |

[13] | Ipopt (2011). (v. 3.10). http://projects.coin-or.org/Ipopt (Accessed 16.12.15). |

[14] | Jowitt, P. W.; Xu, C., Optimal valve control in water-distribution networks, Journal of Water Resources Planning and Management, 116, 4, 455-472, (1990) |

[15] | Lasserre, J., Global optimization problems with polynomials and the problem of moments, SIAM Journal on Optimization, 11, 796-817, (2001) · Zbl 1010.90061 |

[16] | Liberatore, S.; Sechi, G., Location and calibration of valves in water distribution networks using a scatter-search meta-heuristic approach, Water Resources Management, 23, 1479-1495, (2009) |

[17] | Naoum-Sawaya, J.; Ghaddar, B.; Arandia, E.; Eck, B., Simulation optimization approaches for water pump scheduling and pipe replacement problems, European Journal of Operational Research, 246, 1, 293-306, (2015) · Zbl 1346.90553 |

[18] | Nicolini, M.; Zovatto, L., Optimal location and control of pressure reducing valves in water networks, Journal of Water Resources Planning and Management, 135, 3, 178-187, (2009) |

[19] | Reis, L. F.R.; Porto, R. M.; Chaudhry, F. H., Optimal location of control valves in pipe networks by genetic algorithm, Journal of Water Resources Planning and Management, 123, 6, 317-326, (1997) |

[20] | Savic, D. A.; Walters, G. A., An evolution program for optimal pressure regulation in water distribution networks, Engineering Optimization, 24, 3, 197-219, (1995) |

[21] | Sherali, H.; Smith, E., A global optimization approach to a water distribution network design problem, Journal of Global Optimization, 11, 107-132, (1997) · Zbl 0893.90129 |

[22] | Sterling, M.; Bargiela, A., Leakage reduction by optimised control of valves in water networks, Transactions of the Institute of Measurement and Control, 6, 6, 293-298, (1984) |

[23] | Sturm, J., Using sedumi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optimization Methods and Software, 11, 1-4, 625-653, (1999) · Zbl 0973.90526 |

[24] | Vairavamoorthy, K.; Lumbers, J., Leakage reduction in water distribution systems: optimal valve control, Journal of Hydraulic Engineering, 124, 11, 1146-1154, (1998) |

[25] | Waki, H.; Kim, S.; Kojima, M.; Muramatsu, M., Sparsepop: A sparse semidefinite programming relaxation of polynomial optimization problems, ACM Transactions on Mathematical Software, 35, 2, 1-13, (2008) |

[26] | White, F. M., Fluid mechanics, (1999), McGraw-Hill USA |

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.