Article ID: | iaor201522277 |
Volume: | 65 |
Issue: | 1 |
Start Page Number: | 56 |
End Page Number: | 67 |
Publication Date: | Jan 2015 |
Journal: | Networks |
Authors: | Ben-Ameur Walid, Gourdin Eric, Bauguion Pierre-Olivier |
Keywords: | networks: flow, combinatorial optimization, graphs |
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.