A Scalable Shared-Memory Parallel Simplex for Large-Scale Linear Programming

The Simplex tableau has been broadly used and investigated in the industry and academia. With the advent of the big data era, ever larger problems are posed to be solved in ever larger machines whose architecture type did not exist in the conception of this algorithm. In this paper, we present a shared-memory parallel implementation of the Simplex tableau algorithm for dense large-scale Linear Programming (LP) problems for use in modern multi-core architectures. We present the general scheme and explain the strategies taken to parallelize each step of the standard simplex algorithm, emphasizing the solutions found to solve performance bottlenecks. We analyzed the speedup and the parallel efficiency for the proposed implementation relative to the standard Simplex algorithm using a shared-memory system with 64 processing cores. The experiments were performed for several different problems, with up to 8192 variables and constraints, in their primal and dual formulations. The results show that the performance is mostly much better when we use the formulation with more variables than inequality constraints. Also, they show that the parallelization strategies applied to avoid bottlenecks lead the implementation to scale well with the problem size and the core count up to a certain limit of problem size. Further analysis showed that this scaling limit was an effect of resource limitation. Even though, our implementation was able to reach speedups in the order of 19x.