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

The 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