A simplex algorithm for network flow problems with piecewise-linear fractional objective function

The simplex algorithm for network flow problems has been proposed for linear, piecewise linear, and linear fractional objective functions. Piecewise linear fractional network flow problems can be transformed into equivalent linear or linear fractional programs, but the resulting problems do not possess pure network flow structure and increase the number of variables significantly. We develop a simplex algorithm to solve network flow problems with piecewise linear fractional objective function, unifying and generalizing the network simplex algorithm, network simplex algorithm for piece-wise linear programs, and network simplex algorithm for linear fractional programs. Computational results using the proposed algorithm are also discussed.