Nonlinear network optimization on a massively parallel connection machine

Optimization problems with network constraints arise in several instances in engineering, management, statistical and economic applications. The (usually) large size of such problems motivated research in designing efficient algorithms and software for this problem class. The introduction of parallelism in the design of computer systems adds a new element of complexity to the field. This paper describes the implementation of a distributed relaxation algorithm for strictly convex network problems on a massively parallel computer. A Connection Machine CM-1 configured with 16384 processing elements serves as the testbed of the implementation. The authors report computational results with a series of stick percolation and quadratic transportation problems. The algorithm is compared with an implementation of the primal truncated Newton on an IBM 3081-D mainframe, an Alliant FX/8 shared memory vector multiprocessor and the IBM 3090-600 vector supercomputer. One of the larger test problems with approximately 2500 nodes and 8000 arcs requires 1.5 minutes of CPU time on the vector supercomputer. The same problem is solved using relaxation on the CM-1 in less than a second.