Experimental evaluation of algorithmic solutions for generalized network flow models

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.