ALTERNATING DIRECTION SPLITTINGS FOR BLOCK ANGULAR PARALLEL OPTIMIZATION

We develop and compare three decomposition algorithms derived from the method of alternating directions. They may be viewed as block Gauss-S eidel variants of augmented Lagrangian approaches that take advantage of block angular structure. From a parallel computation viewpoint, the y are ideally suited to a data parallel environment. Numerical results for large-scale multicommodity flow problems are presented to demonst rate the effectiveness of these decomposition algorithms on the Thinki ng Machines CM-5 parallel supercomputer relative to the widely-used se rial optimization package MINOS 5.4.