Proportional Equity Flow Problem for Terminal Arcs

The proportional equity flow problem extends a class of problems referred to as equity flow problems whose objective is to equitably distribute flow among the arcs in a flow circulation network. The proportionally bounded flow circulation problem places lower and upper bounds on each arc flow that are nondecreasing continuous functions of the flow through one special arc, and the objective is to maximize the flow through the special arc. The proportional equity flow problem for terminal arcs (Problem TA) is then defined as a special case where all the proportional arcs enter a sink vertex. Applications of both the general problem and Problem TA are given. Two optimality conditions for Problem TA are developed, as well as an algorithm that is polynomially bounded for many types of nondecreasing, continuous, proportional bounding functions. Specifically, the algorithm is shown to be polynomially bounded if the largest root of an equation can be found in polynomial time.