A Flow Augmentation Approach to the Network with Gains Minimum Cost Flow Problem

Abstract

A network with gains has branches in which the ratio between the flow leaving a branch and the flow entering a branch is a positive constant called the gain. Branch gains may be greater or less than one. Such networks arise in water resources and electrical power planning problems, among others. This paper presents a dual method of finding the minimum cost flows in such a network. Computerized versions of the procedure have been tested on networks with up to 7,000 branches.