Efficient algorithms for the maximum concurrent flow problem

Efficient algorithms for the maximum concurrent flow problem

0.00 Avg rating0 Votes
Article ID: iaor201522277
Volume: 65
Issue: 1
Start Page Number: 56
End Page Number: 67
Publication Date: Jan 2015
Journal: Networks
Authors: , ,
Keywords: networks: flow, combinatorial optimization, graphs
Abstract:

In this article, we propose a generic decomposition scheme for the maximum concurrent flow problem. This decomposition scheme encompasses many models, including, among many others, the classical path formulation and the less studied tree formulation, where the flows of commodities sharing a same source vertex are routed on a set of trees. The pricing problem for this generic model is based on shortest‐path computations. We show that the tree‐based linear programming formulation can be solved much more quickly than the path or the aggregated arc‐flow formulation. Some other decomposition schemes can lead to even faster resolution times. Finally, an efficient strongly polynomial‐time combinatorial algorithm is proposed for the single‐source case.

Reviews

Required fields are marked *. Your email address will not be published.