  We present a first step towards a multigrid method for solving the min-cost
flow problem. Specifically, we present a strategy that takes advantage of
existing black-box fast iterative linear solvers, i.e. algebraic multigrid
methods. We show with standard benchmarks that, while less competitive than
combinatorial techniques on small problems that run on a single core, our
approach scales well with problem size, complexity, and number of processors,
allowing for tackling large-scale problems on modern parallel architectures.
Our approach is based on combining interior-point with multigrid methods for
solving the nonlinear KKT equations via Newton's method. However, the Jacobian
matrix arising in the Newton iteration is indefinite and its condition number
cannot be expected to be bounded. In fact, the eigenvalues of the Jacobian can
both vanish and blow up near the solution, leading to a significant slow-down
of the convergence speed of iterative solvers - or to the loss of convergence
at all. In order to allow for the application of multigrid methods, which have
been originally designed for elliptic problems, we furthermore show that the
occurring Jacobian can be interpreted as the stiffness matrix of a mixed
formulation of the weighted graph Laplacian of the network, whose metric
depends on the slack variables and the multipliers of the inequality
constraints. Together with our regularization, this allows for the application
of a black-box algebraic multigrid method on the Schur-complement of the
system.
