| In this thesis, we develop a new parallel primal-dual decomposition algorithm for multi-part linear programming (LP) problems. We first present a parallel decomposition method for two-part models, in which the two master-like subproblems are solved simultaneously in two different processors and generate an upper bound and a lower bound on the original problem at each iteration. These two bounds are monotonically improved and converge to within the prescribed tolerance of the optimal value by exchanging primal and dual information.; Then we extend the basic principles of the two-part algorithm to multi-part models by applying a hierarchical decomposition principle recursively. The original multi-part problem is divided into two aggregated subproblems of lower bound type and upper bound type, and the aggregated subproblems are further divided into two smaller aggregated subproblems of upper bound and lower bound. This bifurcation process continues until there are no subproblems left for further decomposition. The subproblems are solved in different processors simultaneously and work together to reach an optimal point during the iterations by exchanging primal and dual information in the hierarchical way. Convergence and other useful properties of the parallel two-part and multi-part algorithms are proven.; We developed a parallel decomposition solver for problems of two, three or four parts, called WATPAR (WATerloo PARalell), through the use of GAMS, the Regex Library, CPLEX 6.0 and PVM (Parallel Virtual Machine) 3.11 on one IBM RS/6000 workstation and a cluster of four PCs running the Solaris operating system. Several multi-part LP models are tested using WATPAR, and in each of the tests, the new parallel decomposition algorithm converged to an optimal value of the original problem in a finite number of iterations. For some large problems, the new method showed some speedups. |
