%A Renato De Leone
%A Robert R. Meyer
%A Armand Zakarian
%T An epsilon--relaxation algorithm for convex network flow problems
%D Date
%R 95-02
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X A relaxation method for separable convex network flow problems is developed
that is well-suited for problems with large variations in the magnitude
of the nonlinear cost terms. The arcs are partitioned into two sets, one of
which contains only arcs corresponding to strictly convex costs. The
algorithm adjusts flows on the other arcs whenever possible,
and terminates with primal-dual pairs that satisfy complementary slackness
on the strictly convex arc set and $\epsilon$-complementary
slackness on the remaining arcs.
An asynchronous parallel variant of the method is also developed.
Computational results demonstrate that the method is significantly more
efficient on ill-conditioned networks than existing methods, solving
problems with several thousand nonlinear arcs in one second or less.