Extended linear formulation of the pump scheduling problem in water distribution networks

This paper presents a generic non-compact linear programming approximation of the pump scheduling problem in drinking water distribution networks. Instead of relying on the binary on/off status of the pumps, the model draws on the continuous duration of activation of pump combinations, whose entire set is computed in a preprocessing step by ignoring the pressure variation in the water tanks. Preprocessing is accelerated using network partition and symmetry arguments. A combinatorial Benders decompositionbased local search takes the approximated solution as input to derive a feasible solution. Our experiments on two different benchmark sets, with fixedor variable-speed pumps, show the accuracy of the approximated formulation and the ability of the matheuristic to compute near-optimal solutions in seconds, where concurrent, more specialized approaches need minutes or hours.