Analysis of the linear programming gradient method for optimal design of water supply networks

A theoretical analysis of the linear programming (LP) gradient method for optimal design of water distribution networks is presented. The method was first proposed by A. Alperovits and U. Shamir (1977) and has received much attention in the last 10 years. It consists of two stages that are solved in alteration: (1) a LP problem is solved for a given feasible flow distribution and (2) a search is conducted in the space of flow variables, based on the gradient of the objective function (GOF). In this paper a matrix formulation is given for both stages using well‐known graph theory matrices. It is proven that the mathematical expression of the GOF is independent of the choice of the sets of loops and paths along which the head constraints are formulated. This is contrary to the claim made by I. C. Goulter et al. (1986). The original GOF expression is shown to have been an approximation of the steepest direction, but still gives good results. Finally, the search procedure is improved by using the projected gradient method.