A partitioned epsilon-relaxation algorithm for separable convex network flow problems

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.