We study and compare preconditioners available for network interior point methods. We derive upper bounds for the condition number of the preconditioned matrices used in the solution of systems of linear equations defining the algorithm search directions. The preconditioners are tested using PDNET, a state-of-the-art interior point code for the minimum cost network flow problem. … Read more
Networks 39 (2002), 216-231. Citation Networks 39 (2002), 216-231.
In this paper we present a new bound on the min-cut max-flow ratio for multicommodity flow problems. We use a so-called aggregated commodity formulation and an optimal solution to its dual to show our main result. Currently, the best known bound for this ratio is proportional to log(k) where k is the number of origin-destination … Read more
In this work we summarize the basic elements of primal and dual Newton algorithms for network optimization with continuously differentiable (strictly) convex arc cost functions. Both the basic mathematics and implementation are discussed, and hints to important tuning details are made. The exposition assumes that the reader posseses a significant level of prior knowledge in … Read more