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

SN - 1063-7192

VL - 6

SP - 179

EP - 205

JO - Parallel Algorithms and Applications

JF - Parallel Algorithms and Applications

IS - 2-3

ER -