Parallel decomposition of multicommodity flow problems using coercion methods

Abstract

We study the parallel implementation of a decomposition algorithm based on coercion functions, for the multicommodity network flow problem. Alternative designs for the parallel implementation of the algorithm are proposed. We then proceed to develop analytical models for the performance of the algorithm when implemented in parallel. Finally, computational results with the parallel implementation of the algorithm on a CRAY Y-MP are used to validate the models. The algorithm achieves modest speedups, and it solves efficiently some very large problems from a military logistics application.