American Journal of Applied Sciences

Solving Linear Programming Problems on the Parallel Virtual Machine Environment

JrJung Lyu, Hsing Luh and Ming-Chang Lee

DOI : 10.3844/ajassp.2004.90.94

American Journal of Applied Sciences

Volume 1, Issue 2

Pages 90-94


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.


© 2004 JrJung Lyu, Hsing Luh and Ming-Chang Lee. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.