Experimental evaluation of algorithmic solutions for the maximum generalised network flow problem

dc.cclicenceN/Aen
dc.contributor.authorRadzik, Tomasz
dc.contributor.authorYang, Shengxiang
dc.date.acceptance2001-12
dc.date.accessioned2020-01-07T15:32:44Z
dc.date.available2020-01-07T15:32:44Z
dc.date.issued2001-12
dc.description.abstractThe maximum generalised network flow problem is to maximise the net flow into a specified node in a network with capacities and gain-loss factors associated with edges. In practice, input instances of this problem are usually solved using general-purpose linear programming codes, but this may change because a number of specialised combinatorial generalised-flow algorithms have been recently proposed. To complement the known theoretical analyses of these algorithms, we develop their implementations and investigate their actual performance. We focus in this study on Goldfarb, Jin and Orlin's excess-scaling algorithm and Tardos and Wayne's push-relabel algorithm. We develop variants of these algorithms to improve their practical efficiency. We compare the performance of our implementations with implementations of simple, but non-polynomial, combinatorial algorithms proposed by Onaga and Truemper, and with performance of CPLEX, a commercial general-purpose linear programming package.en
dc.funderEPSRC (Engineering and Physical Sciences Research Council)en
dc.identifier.citationRadzik, T. and Yang, S. (2001) Experimental evaluation of algorithmic solutions for the maximum generalised network flow problem. Technical Report No. 2001/54, Department of Computer Science, University of Leicester, UK.en
dc.identifier.urihttps://dora.dmu.ac.uk/handle/2086/19002
dc.language.isoenen
dc.peerreviewedNoen
dc.projectidGR/L81468en
dc.researchinstituteInstitute of Artificial Intelligence (IAI)en
dc.subjectNetwork optimisationen
dc.subjectNetwork flow algorithmen
dc.subjectGeneralised flowen
dc.subjectExperimental evaluationen
dc.titleExperimental evaluation of algorithmic solutions for the maximum generalised network flow problemen
dc.typeTechnical Reporten

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
TR-2001-54.pdf
Size:
315.69 KB
Format:
Adobe Portable Document Format
Description:
Main article
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.2 KB
Format:
Item-specific license agreed upon to submission
Description: