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 w
hich contains only arcs corresponding to strictly convex costs. The algorit
hm adjusts flows on the other arcs whenever possible, and terminates with p
rimal-dual pairs that satisfy complementary slackness on the strictly conve
x arc set and epsilon-complementary slackness on the remaining arcs. An asy
nchronous parallel variant of the method is also developed. Computational r
esults demonstrate that the method is significantly more efficient on ill-c
onditioned networks than existing methods, solving problems with several th
ousand nonlinear arcs in one second or less.