Serial and Parallel Solution of Large Scale Linear Programs by Augmented Lagrangian Successive Overrelaxation

Serial and parallel successive overrelaxatíon (SOR) methods are proposed for the solution of the augmented Lagrangian formulation of the dual of a linear program. With the proposed serial version of the method we have solved linear programs with as many as 125,000 constraints and 500,000 variables in less than 72 hours on a MicroVax Il. A, parallel implementation of the method was carried out on a Sequent Balance 21000 multiprocessor with speedup efiiciency of over 65% for problem sizes of up to 10,000 constraints, 40,000 variables and 1,400,000 nonzero matrix elements.