DATA-LEVEL PARALLEL SOLUTION OF MIN-COST NETWORK FLOW PROBLEMS USING E-RELAXATIONS

We discuss the data-parallel implementation of the epsilon-relaxation algorithm for the solution of min-cost network flow problems. For tran sportation problems a Gauss-Seidel variant is implemented on the two-d imensional communication grid of a massively parallel Connection Machi ne CM-2. For arbitrary network topologies - i.e. transhipment problems - we implement a Jacobi algorithm using the hypercube communication n etwork. A new parallel flow-calculation procedure increases the level of parallelism at every iteration of the algorithm and improves its pe rformance. Extensive computational results are reported with network p roblems with up to 1 million arcs.