An epsilon-relaxation method for separable convex cost generalized networkflow problems

Citation
P. Tseng et Dp. Bertsekas, An epsilon-relaxation method for separable convex cost generalized networkflow problems, MATH PROGR, 88(1), 2000, pp. 85-104
Citations number
34
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
0025-5610 → ACNP
Volume
88
Issue
1
Year of publication
2000
Pages
85 - 104
Database
ISI
SICI code
0025-5610(200006)88:1<85:AEMFSC>2.0.ZU;2-S
Abstract
We generalize the epsilon-relaxation method of [14] for the single commodit y, linear or separable convex cost network flow problem to network flow pro blems with positive gains. The method maintains epsilon-complementary slack ness at all iterations and adjusts the are 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 are or a flow change along a simple cycle. Complexity bounds for the method are de rived. For one implementation employing epsilon-scaling, the bound is polyn omial in the number of nodes N, the number of arcs A, a certain constant Ga mma depending on the are gains, and ln(epsilon(0)/<(epsilon)over bar>), whe re epsilon(0) and <(epsilon)over bar> denote, respectively, the initial and the final tolerance epsilon.