A combinatorial interior point method for network flow problems

For solving minimum cost flow problems, the authors develop a combinatorial interior point method based on a variant of the algorithm of Karmarkar, described in Gonzaga. Gonzaga proposes search directions generated by projecting certain directions onto the nullspace of A. By the special combinatorial structure of networks any projection onto the nullspace of A can be interpreted as a flow in the incremental graph of G. In particular, to evaluate the new search direction, it is sufficient to choose a negative circuit subject to costs on the arcs depending on the current solution. That approach results in an O(mn²L) algorithm where m denotes the number of vertices, n denotes the number of arcs, and L denotes the total length of input data.