Distributed Decomposition of Block-Angular Linear Programs on a Hypercube Computer.

摘要

Algorithms based on the Dantzig-Wolfe decomposition principle for linear programs are implemented on an Intel iPSC-2 Hypercube computer with 64-processors. Computational results with block-angular linear programs from diverse applications are reported. They indicate that the approach of distributed computation on relatively inexpensive multiple processor computers may be very cost-effective for large, structured linear programs. It is also shown that by studying certain characteristics of the interaction among the master and subproblems, one can select algorithms that best exploit the parallel processing environment. Keywords: Large-scale systems; Linear programming decomposition; Parallel processing. (aw)