Efficient Two-Phase Algorithm to Solve Nonconvex MINLP Model of Pump Scheduling Problem

Abstract

In water distribution networks, pumps are used to raise the pressure of water and transfer it throughout the network. Because the cost of electricity consumed by pumps is very high, optimal planning of pumping operations is of great importance. In this paper, the pump scheduling problem is formulated as a mixed integer nonlinear programming (MINLP) model assuming that the flow direction on pipes is not fixed in advance. Due to the hydraulic constraints, the model contains nonlinear terms as the square of continuous variables. Because of the nonconvexity, the MINLP solvers would be unable to find a feasible solution to the moderate- and large-sized instances of the problem in a reasonable time. In this paper, a two-phase method is presented to solve the problem. In the first phase, an initial feasible solution is generated via a heuristic method based on the underlying problem structure. This solution is then fed into the second phase to reach a near-optimal solution. The core part of this algorithm is an iterative approach based on the piecewise McCormick relaxation technique, and to accelerate the method, some techniques such as bound-tightening and the addition of valid inequalities are proposed. Computational experiments on some real-world instances taken from the literature confirm the efficiency of the proposed method compared to MINLP solvers from both solution quality and time.