Parallel network simplex algorithm for the minimum cost flow problem
- 20 October 2021
- journal article
- research article
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 34 (4) , e6659
Abstract
In this work, we contribute a parallel implementation of the network simplex algorithm that is used for the solution of minimum cost flow problem. In the network simplex algorithm, finding an entering arc requires searching through many arcs to decide which one should be included in the spanning tree solution on the next iteration. We propose finding the entering arc in parallel as it often takes the majority of the execution time. A usual strategy is to pick the arc violating the optimality the most out of all possible candidates. Scanning all arcs can take quite some time, so it is common to consider only a fixed number of arcs which is referred as the block search pivoting rule. Arc scans can easily be done in parallel to find the best candidate as the calculations are independent of each other. We used shared memory parallelism using OpenMP along with vectorization using AVX instructions. We also tried adjusting block sizes to increase the parallel portion of the algorithm. Our dataset consists of various natural and synthetic graphs with sizes up to a billion arc. Our experiments show speedups up to four are possible, though they are typically lower.Keywords
This publication has 37 references indexed in Scilit:
- Improving the modulo simplex algorithm for large-scale periodic timetablingComputers & Operations Research, 2013
- Nonlinear fixed charge transportation problem by minimum cost flow-based genetic algorithmComputers & Industrial Engineering, 2012
- LEMON – an Open Source C++ Graph Template LibraryElectronic Notes in Theoretical Computer Science, 2011
- OpenMP: an industry standard API for shared-memory programmingIEEE Computational Science and Engineering, 1998
- The network simplex method on a multiprocessorNetworks, 1990
- Solution of large dense transportation problems using a parallel primal algorithmOperations Research Letters, 1990
- An efficient implementation of the network simplex method1986
- Pivot Strategies for Primal-Simplex Network CodesJournal of the ACM, 1978
- Benefit-Cost Analysis of Coding Techniques for the Primal Transportation AlgorithmJournal of the ACM, 1973
- A High-Speed Computer Technique for the Transportation ProblemJournal of the ACM, 1958