Data-level parallel solution of min-cost network flow problems using ϵ-relaxations

We discuss the data-parallel implementation of the ϵ-relaxation algorithm for the solution of min-cost network flow problems. For transportation problems a Gauss–Seidel variant is implemented on the two-dimensional communication grid of a massively parallel Connection Machine CM-2. For arbitrary network topologies – i.e. transhipment problems – we implement a Jacobi algorithm using the hypercube communication network. A new parallel flow-calculation procedure increases the level of parallelism at every iteration of the algorithm and improves its performance. Extensive computational results are reported with network problems with up to 1 million arcs.