Solving Linear Programming Problems on the Parallel Virtual Machine Environment

Abstract

This study developed a parallel algorithm to efficiently solve linear programming models. The proposed algorithm utilizes the Dantzig-Wolfe Decomposition Principle and can be easily implemented in a general distributed computing environment. The analytical performance of the well-known method; including the speedup upper bound and lower bound limits; was derived. Numerical experiments are also provided in order to verify the complexity of the proposed algorithm. The empirical results demonstrate that the speedup of this parallel algorithm approaches linearity; which means that it can take full advantage of the distributed computing power as the size of the problem increases.