Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/5891
Title: Experimental evaluation of algorithmic solutions for generalized network flow models
Authors: Radzik, T
Yang, S
Keywords: Network optimisation;Network flow algorithms;Generalised flow;Experimental evaluation
Issue Date: 2000
Publisher: Mathematical Programming Society
Citation: 17th International Symposium on Mathematical Programming (ISMP'00), Atlanta, Georgia, 07 - 11 Aug 2000
Abstract: The generalised network flow problem is to maximise the net flow into a specified sink node in a network with gain-loss factors associated with edges. In practice, computation of solutions for instances of this problem is almost always done using general-purpose linear programming codes, but this may change because a number of specialized combinatorial generalised-flow algorithms have been recently proposed. To complement the known theoretical analyses of these algorithms, we develop their implementations and investigate their practical performance. We include in our study different versions of Goldberg, Plotkin, and Tardos's Fat-Path algorithm and Wayne's Push-Related algorithm. We compare the performance of our implementations of these algorithms with implementations of the straightforward highest-gain path-augmentation algorithms. We use various classes of networks, including a type of layered networks which may appear in the multiperiod portfolio revision problem.
Description: Copyright @ 2000 Mathematical Programming Society
URI: http://bura.brunel.ac.uk/handle/2438/5891
Appears in Collections:Publications
Computer Science
Dept of Computer Science Research Papers

Files in This Item:
File Description SizeFormat 
Fulltext.pdf228.4 kBAdobe PDFView/Open


Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.