Pump scheduling in drinking water distribution networks with an LP/NLP-based branch and bound

Gratien Bonvin (1) , Sophie Demassey (1) , Andrea Lodi (2)

1 CMA - Centre de Mathématiques Appliquées
2 EPM - École Polytechnique de Montréal

This paper offers a novel approach for computing globally optimal solutions to the pump scheduling problem in drinking water distribution networks. A tight integer linear relaxation of the original non-convex formulation is devised and solved by branch and bound where integer nodes are investigated through non-linear programming to check the satisfaction of the non-convex constraints and compute the actual cost. This generic method can tackle a large variety of networks , e.g. with variable-speed pumps. We also propose to specialize it for a common subclass of networks with several improving techniques, including a new primal heuristic to repair near-feasible integer relaxed solutions. Our approach is numerically assessed on various case studies of the literature and compared with recently reported results.

Domaines: Recherche opérationnelle [math.OC]; Optimisation et contrôle [math.OC]; Milieux fluides et réactifs

Gratien Bonvin, Sophie Demassey, Andrea Lodi. Pump scheduling in drinking water distribution networks with an LP/NLP-based branch and bound. 2019. ⟨hal-02158535v1⟩