Article ID: | iaor20013645 |
Country: | Germany |
Volume: | 88 |
Issue: | 1 |
Start Page Number: | 85 |
End Page Number: | 104 |
Publication Date: | Jan 2000 |
Journal: | Mathematical Programming |
Authors: | Bertsekas D.P., Tseng P. |
Keywords: | networks: flow |
We generalize the ε-relaxation method for the single commodity, linear or separable convex cost network flow problem to network flow problems with positive gains. The method maintains ε-complementary slackness at all iterations and adjusts the arc flows and the node prices so as to satisfy flow conservation upon termination. Each iteration of the method involves either a price change on a node or a flow change along an arc or a flow change along a simple cycle. Complexity bounds for the method are derived. For one implementation employing ε-scaling, the bound is polynomial in the number of nodes