Abstract

We consider the polymatroidal flow network model which incorporates two important extensions of the standard maximal flow problem: general concave objective functions of the vector of supplies to a collection of sinks, as well as polymatroidal capacity restrictions on sets of arcs emanating from or pointing to a common node. A number of important applications are reviewed. We show that in this general model the set of feasible supply vectors is itself a polymatroid, and that an optimal solution may be determined by at most 2|V*| – 1 maximum flow computations and optimizations of the objective over a single budget constraint, where |V*| is the number of sinks. Also, it is shown that for the most common types of polymatroidal structures an equivalent flow network can be constructed on an expanded graph but with capacity restrictions on individual arcs only. This transformation allows for the use of classical maximum flow procedures resulting in an often dramatic reduction in complexity.

Authors
Awi Federgruen and Henri Groenevelt
Format
Journal Article
Publication Date
Journal
Networks

Full Citation

Federgruen, Awi and Henri Groenevelt
. “Polymatroidal flow network models with multiple sinks.”
Networks
vol.
18
, (January 01, 1988):
285
-
302
.