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.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
|Titolo:||Implementation and Test of Auction Methods for Solving Generalized Network Flow Problems with Separable Convex Cost|
|Data di pubblicazione:||2002|
|Appare nelle tipologie:||1.1 Articolo in rivista|