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

F. Guerriero and P. Tseng
Additional contact information
F. Guerriero: Università della Calabria
P. Tseng: University of Washington

Journal of Optimization Theory and Applications, 2002, vol. 115, issue 1, No 8, 113-144

Abstract: 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.

Keywords: Generalized network flow; ∈-relaxation method; auction sequential shortest path algorithm; implementation; computation (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1023/A:1019629113986 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:115:y:2002:i:1:d:10.1023_a:1019629113986

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1023/A:1019629113986

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().