The parallel decomposition of linear programs
Robert Entriken · 1989
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 programs, 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 code 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. 57 refs., 33 figs., 14 tabs.