A least‐squares minimum‐cost network flow algorithm

Node‐arc incidence matrices in network flow problems exhibit several special least‐squares properties. We show how these properties can be leveraged in a least‐squares primal‐dual algorithm for solving minimum‐cost network flow problems quickly. Computational results show that the performance of an upper‐bounded version of the least‐squares minimum‐cost network flow algorithm with a special dual update operation is comparable to CPLEX Network and Dual Optimizers for solving a wide range of minimum‐cost network flow problems.