PARALLELIZATION STRATEGIES OF A ROW-ACTION METHOD FOR MULTICOMMODITY NETWORK FLOW PROBLEMS
- 1 January 1995
- journal article
- research article
- Published by Taylor & Francis in Parallel Algorithms and Applications
- Vol. 6 (2-3) , 179-205
- https://doi.org/10.1080/10637199508915508
Abstract
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.Keywords
This publication has 25 references indexed in Scilit:
- Algorithms for nonlinear multicommodity network flow problemsPublished by Springer Nature ,2005
- Interval-constrained matrix balancingLinear Algebra and its Applications, 1991
- Optimization of Burg's entropy over linear constraintsApplied Numerical Mathematics, 1991
- An Empirical Evaluation of the KORBX® Algorithms for Military Airlift ApplicationsOperations Research, 1990
- Parallel optimization for traffic assignmentMathematical Programming, 1988
- Relaxation Methods for Network Flow Problems with Convex Arc CostsSIAM Journal on Control and Optimization, 1987
- Row-Action Methods for Huge and Sparse Systems and Their ApplicationsSIAM Review, 1981
- An iterative row-action method for interval convex programmingJournal of Optimization Theory and Applications, 1981
- Multicommodity network flows—A surveyNetworks, 1978
- Validity of the single processor approach to achieving large scale computing capabilitiesPublished by Association for Computing Machinery (ACM) ,1967