Parallel implementation of a central decomposition method for solving large-scale planning problems

We use a decomposition approach to solve three types of realistic problems: block-angular linear programs arising in energy planning, Markov decision problems arising in production planning and multicommodity network problems arising in capacity planning for survivable telecommunication networks. De composition is an algorithmic device that breaks down computations into sev eral independent subproblems. It is thus ideally suited to parallel impleme ntation. To achieve robustness and greater reliability in the performance o f the decomposition algorithm, we use the Analytic Center Cutting Plane Met hod (ACCPM) to handle the master program. We run the algorithm on two diffe rent parallel computing platforms: a network of PC's running under Linux an d a genuine parallel machine, the IBM SP2. The approach is well adapted for this coarse grain parallelism and the results display good speed-up's for the classes of problems we have treated.