Parallel solution of large-scale, block-angular linear programs

Many important large-scale optimization problems can be formulated as linear programs with a block-angular structure. This structure lends itself naturally to parallel solutions and is used to great advantage in the solution method described. To demonstrate the efficiency of the method, it has been implemented and computationally tested on both a shared-memory vector multiprocessor (CRAY-2) and a local-memory hypercube (NCUBE/seven) with 64 processors. Computational results for problems with as many as 24000 rows and 74000 columns (1024 blocks and 1.4 million nonzero elements) are presented. A problem of this size was solved on the NCUBE in less than four minutes and the CRAY-2 in 37 seconds.