TY - GEN

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

AU - Tseng, Paul

AU - Bertsekas, Dimitri P.

PY - 1996

Y1 - 1996

N2 - We propose an extension of the ε-relaxation method to generalized network flow problems with separable convex cost. The method maintains ε-complementary slackness satisfied at all iterations and adjusts the arc flows and the node prices so to satisfy flow conservation upon termination. Each iteration of the method involves either a price change at a node or a flow change at an arc or a flow change around 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 ε.

AB - We propose an extension of the ε-relaxation method to generalized network flow problems with separable convex cost. The method maintains ε-complementary slackness satisfied at all iterations and adjusts the arc flows and the node prices so to satisfy flow conservation upon termination. Each iteration of the method involves either a price change at a node or a flow change at an arc or a flow change around 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 ε.

UR - http://www.scopus.com/inward/record.url?scp=84947904206&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947904206&partnerID=8YFLogxK

U2 - 10.1007/3-540-61310-2_7

DO - 10.1007/3-540-61310-2_7

M3 - Conference contribution

AN - SCOPUS:84947904206

SN - 3540613102

SN - 9783540613107

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 85

EP - 93

BT - Integer Programming and Combinatorial Optimization - 5th International IPCO Conference, 1996 Proceedings

A2 - Cunningham, William H.

A2 - McCormick, S.Thomas

A2 - Queyranne, Maurice

PB - Springer Verlag

T2 - 5th International Conference Integer Programming and Combinatorial Optimization, IPCO 1996

Y2 - 3 June 1996 through 5 June 1996

ER -