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.

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

GUERRIERO, Francesca;
2002

Abstract

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/137152
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 6
social impact