An ε-relaxation method for separable convex cost generalized network flow problems

An ε-relaxation method for separable convex cost generalized network flow problems

0.00 Avg rating0 Votes
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: ,
Keywords: networks: flow
Abstract:

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 N, the number of arcs A, a certain constant Γ depending on the arc gains, and ln(ε0/ε), where ε0 and ε denote, respectively, the initial and the final tolerance &epsimacr;.

Reviews

Required fields are marked *. Your email address will not be published.