Implementation and Test of Auction Methods for Solving Generalized Network Flow Problems with Separable Convex Cost

We describe the implementation and testing of two methods, based on the auction approach, for solving the problem of minimizing a separable convex cost subject to generalized network flow conservation constraints. The first method is the relaxation method of Ref. 1; the second is an extension of the auction sequential_shortest path algorithm for ordinary network flow to generalized network flow. We report test results on a large set of randomly generated problems with varying topology, arc gains, and cost function. Comparison with the commercial code CPLEX on linear_quadratic cost problems and with the public domain code PPRN on nonlinear cost ordinary network problems are also made. The test results show that the auction sequential_shortest path algorithm is generally fastest for solving quadratic cost problems and mixed linear_nonlinear cost problems with arc gain range near 1. The relaxation method is generally fastest for solving nonlinear cost ordinary network problems and mixed linear_nonlinear cost problems with arc gain range away from 1. CPLEX is generally fastest for solving linear cost and mixed linear_quadratic cost problems with arc gain range near 1.