TY - JOUR
T1 - Parallelization strategies of a row-action method for multicommodity network flow problems
AU - Censor, Yair
AU - Chajakis, Emmanuel D.
AU - Zenios, Stavros A.
PY - 1995/1/1
Y1 - 1995/1/1
N2 - We develop a decomposition algorithm for the quadratic multicommodity network flow problem, using a row-action primal-dual algorithm. The algorithm decomposes the problem first by commodity and then by arc. Hence, it is suitable for parallel implementations. We study two parallelization strategies of this algorithm. These are the “parallelization within a commodity” (PWC) and the “parallelization across commodities” (PAC). Both strategies are evaluated empirically. Extensive computational results indicate that (1) the row-action algorithm is efficient for a wide range of problem characteristics, (2) the algorithm achieves almost linear speedup on a small scale parallel architecture, and (3) the algorithm can solve efficiently very large problems, with up to 4000 nodes, 80000 arcs and 80 commodities.
AB - We develop a decomposition algorithm for the quadratic multicommodity network flow problem, using a row-action primal-dual algorithm. The algorithm decomposes the problem first by commodity and then by arc. Hence, it is suitable for parallel implementations. We study two parallelization strategies of this algorithm. These are the “parallelization within a commodity” (PWC) and the “parallelization across commodities” (PAC). Both strategies are evaluated empirically. Extensive computational results indicate that (1) the row-action algorithm is efficient for a wide range of problem characteristics, (2) the algorithm achieves almost linear speedup on a small scale parallel architecture, and (3) the algorithm can solve efficiently very large problems, with up to 4000 nodes, 80000 arcs and 80 commodities.
KW - Multicommodity
KW - Network flows
KW - Parallel optimization
KW - Row-action algorithm
UR - http://www.scopus.com/inward/record.url?scp=77956658286&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77956658286&partnerID=8YFLogxK
U2 - 10.1080/10637199508915508
DO - 10.1080/10637199508915508
M3 - Article
AN - SCOPUS:77956658286
SN - 1063-7192
VL - 6
SP - 179
EP - 205
JO - Parallel Algorithms and Applications
JF - Parallel Algorithms and Applications
IS - 2-3
ER -