Distributed algorithms for linear programming

In recent years there has been an increasing use of parallel computers to solve problems in many scientific and engineering disciplines. The impact of parallel computers on large-scale computing is beginning to affect the area of mathematical programming. Our primary goal in this dissertation is to adapt the revised simplex method for solving linear programs on a class of parallel computers, called distributed computers. The work consist of two parts. First, we study the serial revised simplex algorithm and provide mathematical characterizations of how time is spent in the algorithm and its modules. We refer to such characterizations as timing models. In the second part of the work, we design revised-simplex-based algorithms for tasks such as reinversion, dual vector computation, pricing, pivot row selection and solution updating. Using the timing models, the speedup provided by these algorithms are inferred. We select 35 medium-sized problems from NETLIB [Gay (1985)] to test and validate our timing models and algorithms. Over the test problems, the speedups provided by our algorithms on the iPSC/2 (an example of a distributed computer) range from 5% to 41% and is 31% on the average.