Combinatorial interior point methods for generalized network flow problems

Combinatorial interior point methods for generalized network flow problems

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

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 O(m2n2(logm + log2n)L) time, where m and n are, respectively, the number of arcs and nodes in the graph, and L is the length of the input data.

Reviews

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