The Alternating Step Method for Monotropic Programming on the Connection Machine CM-2

Abstract

The alternating step method is a massively parallel alternating direction method for monotropic programming, that is, convex programming with a separable objective function and linear constraints. This paper specializes the alternating step method to generalized network problems with positive semi-definite quadratic arc costs, and describes its implementation on a massively parallel computer, the Connection Machine CM-2. Extensive computational tests reveal that while the method is disappointingly slow for most problems with purely linear cost functions, it is competitive with dual relaxation methods on many problems having positive definite objectives. Furthermore, the algorithm continues to perform well even if a minority of arcs are given purely linear costs. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.