A minimum mean cycle cancelling method for nonlinear multicommodity flow problems

We propose a new method based on minimum mean cycle cancelling for multicommodity flow problems with separable convex cost ruling out saturated capacities. This method is inspired by the cycle cancelling method first worked out by Goldberg and Tarjan for minimum cost circulations. Convergence of the method is formally proved and a variant with a more flexible selection of cycles is proposed. Also, we report some computational experience on the message routing problem in telecommunication networks using actual and randomly generated networks.