Article ID: | iaor20032533 |
Country: | Germany |
Volume: | 93 |
Issue: | 2 |
Start Page Number: | 227 |
End Page Number: | 246 |
Publication Date: | Jan 2002 |
Journal: | Mathematical Programming |
Authors: | Goldfarb D., Lin Y. |
Keywords: | networks: flow |
We present combinatorial interior point methods for the generalized minimum cost flow and the generalized circulation problems based on Wallacher and Zimmermann's combinatorial interior point method for the minimum cost network flow problem. The algorithms have features of both a combinatorial algorithm and an interior point method. They work towards optimality by iteratively reducing the value of a potential function while maintaining interior point solutions. At each iteration, flow is augmented along a generalized circulation, which is computed by solving a TVPI (Two Variables Per Inequality) system. The algorithms run in