Parallel Arc-Allocation Algorithms for Optimizing Generalized Networks

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 multitree structure of basic solutions and perform 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. 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