Parallel arc-allocation algorithms for optimizing generalized networks

Parallel arc-allocation algorithms for optimizing generalized networks

0.00 Avg rating0 Votes
Article ID: iaor1990275
Country: Switzerland
Volume: 22
Start Page Number: 129
End Page Number: 160
Publication Date: Jan 1990
Journal: Annals of Operations Research
Authors: ,
Abstract:

Two parallel shared-memory algorithms are presented for the optimization of generalized networks. These algorithms are based on the allocation of arc-related operations in the (generalized) network simplex method. One method takes advantage of the multi-tree structure of basic solutions and performs pivot operations in parallel, utilizing locking to ensure correctness. The other algorithm utilizes only one processor for sequential pivoting, but parallelizes the pricing operation and overlaps this task with pivoting in a speculative manner (i.e. since pivoting and pricing involve data dependencies, a candidate for flow change generated by the pricing processors is not guaranteed to be acceptable, but in practice generally has this property). The relative performance of these two methods (on the Sequent Symmetry S81 multiprocessor) is compared and contrasted with that of a fast sequential algorithm on a set of large-scale test problems of up to 1000000 arcs.

Reviews

Required fields are marked *. Your email address will not be published.