DISTRIBUTED NESTED DECOMPOSITION OF STAIRCASE LINEAR-PROGRAMS

This article considers the application of a primal nested-decompositio n method to solve staircase linear programs (SLPs) on distributed-memo ry, multiple-instruction-multiple-data computers. Due to the coupling that exists among the stages of an SLP, a standard parallel-decomposit ion algorithm for these problems would allow only a subset of the subp roblem processes to overlap with one another at any give time. We prop ose algorithms that seek to increase the amount of overlap among the p rocesses as well as utilize idle time beneficially. Computational resu lts testing the effectiveness of our algorithms are reported, using a standard set of test problems.