An algorithm for Water distribution analysis based on a minimum-cost flow algorithm

This paper proposes an efficient minimum-cost flow algorithm based on the primal-dual simplex method for non-linear convex optimization on networks. After approximating the edge characteristics by a step function, the primal-dual algorithm is executed by making use of the network structure. The algorithm searches igeratively for the shortest-paht tree at each stage. The paper shows that the difference between the i-th tree and the (i+1)-th tree is one elementary transformation under certain restrictions on the approximating function. It proposes an algorithm using this fact. The time complexity of each tree search is of linear order with respect to the number of vertices and edges of the network. The algorithm is applicable for network optimization problems having non-linear convex functions. [In Japanese.]