The Alternating Step Method for Monotropic Programming on the Connection Machine CM-2
ORSA Journal on Computing · 1993 · Volume 5 · Issue 1
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.
Keywords
computers, parallel, connection machine, Networks, generalized networks, flow algorithms, programming, quadratic, separable semidefinite
Enable JavaScript for citation tools and additional paper interactions.