Accession Number : ADA290221

Title :   Solving Linear Programs Using Distributed Parallel Computing.

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA GRADUATE SCHOOL OF INDUSTRIAL ADMINISTRATI ON

Personal Author(s) : Natraj, N. R. ; Thompson, G. L. ; Harche, F.

PDF Url : ADA290221

Report Date : NOV 1994

Pagination or Media Count : 25

Abstract : Parallel and distributed computing has attracted a lot of attention from researchers over the past few years. It is a promising new approach for solving large problems that were hitherto considered very difficult to solve using traditional serial computers. The advancement of technology and the introduction of fiber-optic networks for high speed data transmission has made distributed computing on a network of computers very attractive. In this paper we address the problem of solving linear programs using distributed computing. We present a 2-phase parallel standard simplex algorithm for solving linear programs with single upper bounded variables. The parallel simplex algorithm was implemented on NECTAR (NEtwork CompuTer ARchitecture) a collection of SUN4/33O workstations on a fiber-optic network and evaluated using randomly generated problems and those available from the nedib database.

Descriptors :   *LINEAR PROGRAMMING, *PARALLEL PROCESSING, DATA BASES, ALGORITHMS, FIBER OPTICS, DATA PROCESSING, HIGH RATE, DISTRIBUTED DATA PROCESSING, COMPUTERS, COMPUTER ARCHITECTURE, PROBLEM SOLVING, VARIABLES, COMPUTER NETWORKS, TRANSMITTING, SERIAL PROCESSORS, SIMPLEX METHOD.

Subject Categories : Computer Hardware
      Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE