Minimizing a linear multiplicative-type function under network flow constraints

In this paper, we consider a special class of nonconvex network flow problems, whose objective function is a product of two affine functions. This problem arises when one tries to send as much flow as possible in an ordinary two-terminal network at the minimum possible cost. We will show that a primal–dual algorithm can generate a globally optimal solution in pseudo-polynomial time and a globally ϵ-optimal solution in polynomial time.