PARALLEL SIMPLEX FOR LARGE PURE NETWORK PROBLEMS - COMPUTATIONAL TESTING AND SOURCES OF SPEEDUP

• 成果类型: Article
• 署名作者: BARR, RS; HICKMAN, BL
• 署名单位: University of Nebraska System
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.42.1.65
• 发表日期: 1994
• 页码: 65-80
• 关键词: COMPUTERS COMPUTER SCIENCE; software; SHARED-MEMORY PARALLEL PROCESSING SOFTWARE; networks; FLOW ALGORITHMS; PRIMAL SIMPLEX ALGORITHM FOR PURE NETWORKS; programming; large-scale systems; OPTIMIZATION OF LARGE TIME-CRITICAL NETWORKS

摘要

This paper reports on a new parallel implementation of the primal simplex method for minimum cost network flow problems that decomposes both the pivoting and pricing operations. The self-scheduling approach is flexible and efficient; its implementation is close in speed to the best serial code when using one processor, and is capable of substantial speedups as parallel computing units are added. An in-depth computational study of randomly generated transportation and transshipment problems verified the effectiveness of this approach, with results on a 20-processor 80386-based system that are competitive with, and occasionally superior to, massively parallel implementations using tens of thousands of processors. A microanalysis of the code's behavior identified unexpected sources of (the occasionally superlinear) speedup, including the evolutionary topology of the network basis.