Symmetric and Asymmetric Parallelization of a Cost-Decomposition Algorithm for Multi-Commodity Flow Problems

Abstract: We study the coarse-grained parallelization of a Bundle-based cost decomposition algorithm for the solution of linear Multicommodity Min Cost Flow problems, that has already been shown to be effective in sequential. The aim of the study was to investigate if exploitation of the natural parallelism inherent in the cost decomposition method, i.e. the simultaneous solution of the Min Cost Flow subproblems, was enough to obtain acceptable efficiencies without modifying the basic approach: as a result, we obtained an highly portable and flexible code which can be used on different machines. The computational results show that satisfactory efficiencies can be obtained even with many processors on large, difficult MMCF problems with many commodities, that are exactly the class of instances where the sequential code attains the best results. We also show how to exploit a common characteristic of nowadays supercomputer facilities, i.e. the side-to-side availability of massively parallel and powerful vector supercomputers, by implementing an asymmetric decomposition algorithm where each architecture is used for the tasks it is suited most.