A Lagrangian decomposition approach for the pump scheduling problem in water networks.

*(English)*Zbl 1339.90135Summary: Dynamic pricing has become a common form of electricity tariff, where the price of electricity varies in real time based on the realized electricity supply and demand. Hence, optimizing industrial operations to benefit from periods with low electricity prices is vital to maximizing the benefits of dynamic pricing. In the case of water networks, energy consumed by pumping is a substantial cost for water utilities, and optimizing pump schedules to accommodate for the changing price of energy while ensuring a continuous supply of water is essential. In this paper, a Mixed-Integer Non-linear Programming (MINLP) formulation of the optimal pump scheduling problem is presented. Due to the non-linearities, the typical size of water networks, and the discretization of the planning horizon, the problem is not solvable within reasonable time using standard optimization software. We present a Lagrangian decomposition approach that exploits the structure of the problem leading to smaller problems that are solved independently. The Lagrangian decomposition is coupled with a simulation-based, improved limited discrepancy search algorithm that is capable of finding high quality feasible solutions. The proposed approach finds solutions with guaranteed upper and lower bounds. These solutions are compared to those found by a mixed-integer linear programming approach, which uses a piecewise-linearization of the non-linear constraints to find a global optimal solution of the relaxation. Numerical testing is conducted on two real water networks and the results illustrate the significant costs savings due to optimizing pump schedules.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

90C06 | Large-scale problems in mathematical programming |

90C10 | Integer programming |

90B10 | Deterministic network models in operations research |

PDF
BibTeX
Cite

\textit{B. Ghaddar} et al., Eur. J. Oper. Res. 241, No. 2, 490--501 (2015; Zbl 1339.90135)

Full Text:
DOI

##### References:

[1] | Ampl. (2011). http://www.ampl.com/ Accessed 16.12.2013. |

[2] | Aykin, T., Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem, European Journal of Operational Research, 79, 3, 501-523, (1994) · Zbl 0813.90074 |

[3] | Bonami, P.; Biegler, L. T.; Conn, A. R.; Cornuéjols, G.; Grossmann, I. E.; Laird, C. D., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optimization, 5, 2, 186-204, (2008) · Zbl 1151.90028 |

[4] | Bonmin (v. 1.5). (2011). http://projects.coin-or.org/Bonmin Accessed 16.12.2013. |

[5] | 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 |

[6] | Brion, L. M.; Mays, L. W., Methodology for optimal operation of pumping stations in water distribution systems, Journal of Hydraulic Engineering, 117, 11, 1551-1569, (1991) |

[7] | D’Ambrosio, C.; Lodi, A.; Wiese, S.; Bragalli, C., Mathematical programming techniques in water network optimization, European Journal of Operational Research, (2014) |

[8] | de la Perrière, L. B.; Jouglet, A.; Nace, A.; Nace, D., Water planning and management: an extended model for the real-time pump scheduling problem, Advances in hydroinformatics, 153-170, (2014), Springer |

[9] | Denig-Chakroff, D. (2008). Reducing electricity used for water production: Questions state commissions should ask regulated utilities: Technical report. National Regulatory Research Institute. |

[10] | Detienne, B., A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints, European Journal of Operational Research, 235, 3, 540-552, (2014) · Zbl 1305.90179 |

[11] | Diabat, A., Abdallah, T., & Henschel, A. (in press). A closed-loop location-inventory problem with spare parts consideration. Computers & Operations Research. DOI: · Zbl 1348.90081 |

[12] | Eck, B.; Mevissen, M., Fast non-linear optimization for design problems on water networks, World environmental and water resources congress 2013, 696-705, (2013) |

[13] | Eiger, G.; Shamir, U.; Ben-Tal, A., Optimal design of water distribution networks, Water Resources Research, 30, 9, 2637-2646, (1994) |

[14] | Elhedhli, S.; Li, L.; Gzara, M.; Naoum-Sawaya, J., A branch-and-price algorithm for the bin packing problem with conflicts, INFORMS Journal on Computing, 23, 3, 404-415, (2011) · Zbl 1243.90089 |

[15] | EPANET (v. 2). (2008). http://www.epa.gov/nrmrl/wswrd/dw/epanet.html Accessed 16.12.2013. |

[16] | Fisher, M. L., The Lagrangian relaxation method for solving integer programming problems, Management Science, 50, 12, 1861-1871, (2004) |

[17] | Geoffrion, A. M., Lagrangian relaxation for integer programming, 50 Years of integer programming 1958-2008, 243-281), (2010), Springer · Zbl 1187.90010 |

[18] | Giacomello, C.; Kapelan, Z.; Nicolini, M., Fast hybrid optimization method for effective pump scheduling, Journal of Water Resources Planning and Management, 139, 2, 175-183, (2012) |

[19] | Gleixner, A.; Held, H.; Huang, W.; Vigerske, S., Towards globally optimal operation of water supply networks, Numerical Algebra, Control and Optimization, 2, 4, 695-711, (2012) · Zbl 1269.90083 |

[20] | Gzara, F.; Erkut, E., A Lagrangian relaxation approach to large-scale flow interception problems, European Journal of Operational Research, 198, 2, 405-411, (2009) · Zbl 1163.90814 |

[21] | Harvey, W. D.; Ginsberg, M. L., Limited discrepancy search, Proceedings of the 14th international joint conference on artificial intelligence (IJCAI’95), 607-615), (1995) |

[22] | IBM ILOG CPLEX Optimization Studio. (2013). http://www-03.ibm.com/software/products/us/en/ibmilogcpleoptistud/ Accessed 16.12.2013. |

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

[24] | Jowitt, P. W.; Germanopoulos, G., Optimal pump scheduling in watersupply networks, Journal of Water Resources Planning and Management, 118, 4, 406-422, (1992) |

[25] | Korf, R. E., Improved limited discrepancy search, Proceedings of the 13th national conference on artificial intelligence (AAAI’96), 1202-1207), (1996) |

[26] | Lansey, K. E.; Awumah, K., Optimal pump operations considering pump switches, Journal of Water Resources Planning and Management, 120, 1, 17-35, (1994) |

[27] | López-Ibáñez, M.; Prasad, T. D.; Paechter, B., Ant colony optimization for optimal control of pumps in water distribution networks, Journal of Water Resources Planning and Management, 134, 4, 337-346, (2008) |

[28] | McCormick, G.; Powell, R., Optimal pump scheduling in water supply systems with maximum demand charges, Journal of Water Resources Planning and Management, 129, 5, 372-379, (2003) |

[29] | McCormick, G.; Powell, R., Derivation of near-optimal pump schedules for water distribution by simulated annealing, Journal of the Operational Research Society, 55, 7, 728-736, (2004) · Zbl 1095.90044 |

[30] | National Geographic. (2013). http://news.nationalgeographic.com/news/energy/2013/01/130130-water-demand-forenergy-to-double-by-2035/ Accessed 16.12.2013. |

[31] | Nitivattananon, V.; Sadowski, E. C.; Quimpo, R. G., Optimization of water supply system operation, Journal of Water Resources Planning and Management, 122, 5, 374-384, (1996) |

[32] | Richmond Water Distribution Network. (2013). http://emps.exeter.ac.uk/engineering/research/cws/downloads/benchmarks/ Accessed 16.12.2013. |

[33] | Sakarya, A. B.A.,; Mays, L. W., Optimal operation of water distribution pumps considering water quality, Journal of Water Resources Planning and Management, 126, 4, 210-220, (2000) |

[34] | Single Electricity Market Operator. (2013). http://www.sem-o.com Accessed 16.12.2013. |

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

[36] | Sherali, H. D.; Smith, E. P.; Kim, S.-I., A pipe reliability and cost model for an integrated approach toward designing water distribution systems, Global optimization in engineering design, 333-354, (1996), Springer · Zbl 0874.90123 |

[37] | Sherali, H. D.; Subramanian, S.; Loganathan, G. V., Effective relaxations and partitioning schemes for solving water distribution network design problems to global optimality, Journal of Global Optimization, 19, 1, 1-26, (2001) · Zbl 0967.90087 |

[38] | Ulanicki, B.; Kahler, J.; See, H., Dynamic optimization approach for solving an optimal scheduling problem in water distribution systems, Journal of Water Resources Planning and Management, 133, 1, 23-32, (2007) |

[39] | Wang, S.; Huang, G. H., A two-stage mixed-integer fuzzy programming with interval-valued membership functions approach for flood-diversion planning, Journal of Environmental Management, 117, 208-218, (2013) |

[40] | Wang, S.; Huang, G. H.; Yang, B. T., An interval-valued fuzzy-stochastic programming approach and its application to municipal solid waste management, Environmental Modelling & Software, 29, 1, 24-36, (2012) |

[41] | Yu, G.; Powell, R. S.; Sterling, M. J.H., Optimized pump scheduling in water distribution systems, Journal of Optimization Theory and Applications, 83, 3, 463-488, (1994) · Zbl 0813.90130 |

[42] | Zessler, U.; Shamir, U., Optimal operation of water distribution systems, Journal of Water Resources Planning and Management, 115, 6, 735-752, (1989) |

[43] | Zheng, X.; Sun, X.; Li, D.; Cui, X., Lagrangian decomposition and mixed-integer quadratic programming reformulations for probabilistically constrained quadratic programs, European Journal of Operational Research, 221, 1, 38-48, (2012) · Zbl 1253.90182 |

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.