Treffer: 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 16,384 processing elements serves as the testbed of the implementation. We 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 that a second. [ABSTRACT FROM AUTHOR]

Copyright of Annals of Operations Research is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)