A Primal Algorithm for Finding Minimum-Cost Flows in Capacitated Networks With Applications
Clyde L. Monma, Michael Segal · Bell System Technical Journal · 1982
Algorithms for finding a minimum-cost, single-commodity flow in a capacitated network are based on variants of the simplex method of linear programming. We describe an implementation of a primal algorithm which is fast and can solve large problems. The major ideas incorporated are (i) the sparsity of the network is used to reduce the time and computer storage space requirements; (ii) basic solutions are stored compactly as spanning trees of the network; (iii) a candidate stack is used to allow flexible strategies in choosing an arc to enter the basis tree; (iv) the predecessor and thread data structures are used to efficiently traverse the tree and to update the solution at each iteration; (v) rules are implemented to avoid cycling or stalling caused by degeneracy; and (vi) piecewise-linear, convex arc costs are handled implicitly. The Primal Network Flow Convex (PNFC) code implements this algorithm and three examples, from communication networks, that can be solved with PNFC are discussed: (i) solving the area transfer problem; (ii) scheduling the collection of traffic data records; and (iii) planning the placement of pair-gain systems.