Parallel arc-allocation algorithms for optimizing generalized networks

Autor:	R. R. Meyer, R. H. Clark
Rok vydání:	1990
Předmět:	Set (abstract data type) Task (computing) Correctness Simplex algorithm Computer science Basic solution Theory of computation General Decision Sciences Multiprocessing Management Science and Operations Research Algorithm Sequential algorithm
Zdroj:	Annals of Operations Research. 22:129-160
ISSN:	1572-9338 0254-5330
DOI:	10.1007/bf02023051
Popis:	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 1,000,000 arcs.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::bba4b80ed24e4c9183c2b0c67ac08238 https://doi.org/10.1007/bf02023051 Zobrazit plný text záznamu Plný text ve formátu PDF