Accelerated dual coordinate algorithms for separable convex cost network flow problems

Nonlinear network flow problems are convex minimization problems that arise in diverse applications from transportation to finance. The network structure of the constraints and the separability of objectives make this class of problems suitable for special algorithms that are orders of magnitude faster than standard convex optimization methods. Dual coordinate algorithms such as ϵ-relaxation are among the fastest methods for solving such separable convex cost network flow problems. In this paper, we identify conditions where the ϵ-relaxation algorithm is inefficient and requires many iterations to make progress towards convergence. We subsequently develop a new algorithm that avoids such conditions while preserving the advantages of the original ϵ-relaxation algorithm. It is inspired by techniques used in the auction algorithm for linear assignment problems. We show that our new algorithm is correct and shares the same worst-case complexity as the original algorithm. Through extensive numerical experiments on benchmark problems we demonstrate that our new algorithm significantly reduces computation times over the original algorithm because it replaces many steps of ϵ-relaxation by a single large step.