The Parallel of Decomposition of Linear Programs

Abstract
This thesis introduces a new calculus for manipulating linear-program decomposition schemes. A linear program is represented by a communication network, which is decomposed by splitting nodes in two, and a transformation is defined to recover subproblems from the network. We also define a dual-symmetric oracle that provides solutions to linear program, and can be performed by the simplex method, nested decomposition, and finally, parallel decomposition. Two important classes of linear program serve as examples for the above calculus: staircase linear programs and stochastic linear programs. For the former case, a sophisticated yet experimental computer codes has been written for an IBM 3090/ 600E with six processors. The code performs the parallel decomposition algorithm and is tested on twenty-two small to medium sized real-world problems. Experiments show that in addition to speedups provided by decomposition alone, performance is improved by using parallel processors.

This publication has 0 references indexed in Scilit: