TY - JOUR
T1 - A new model for multicommodity flow problems, and a strongly polynomial algorithm for single-source maximum concurrent flow
AU - Bauguion, Pierre Olivier
AU - Ben-Ameur, Walid
AU - Gourdin, Eric
PY - 2013/7/9
Y1 - 2013/7/9
N2 - In this paper, a new decomposition approach is proposed to solve large size instances of Multicommodity Flow problems. Instead of generating paths, we generate trees in a convenient way. Numerical results show that the new approach is much more efficient than the classical paths generation approach. Moreover, we propose a combinatorial polynomial-time algorithm to solve the maximum concurrent flow problem (MCF) in the single-source case.
AB - In this paper, a new decomposition approach is proposed to solve large size instances of Multicommodity Flow problems. Instead of generating paths, we generate trees in a convenient way. Numerical results show that the new approach is much more efficient than the classical paths generation approach. Moreover, we propose a combinatorial polynomial-time algorithm to solve the maximum concurrent flow problem (MCF) in the single-source case.
KW - Column generation
KW - Maximum concurrent flow
KW - Tree packing
U2 - 10.1016/j.endm.2013.05.107
DO - 10.1016/j.endm.2013.05.107
M3 - Article
AN - SCOPUS:84879704215
SN - 1571-0653
VL - 41
SP - 311
EP - 318
JO - Electronic Notes in Discrete Mathematics
JF - Electronic Notes in Discrete Mathematics
ER -