Brunel University Research Archive (BURA) >
University >
Publications >

Please use this identifier to cite or link to this item:

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
Publication 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
Sponsorship: This work was supported by the EPSRC grant GR/L81468
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.