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 | Size | Format | |
---|---|---|---|---|
Fulltext.pdf | 228.4 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.