J. Gondzio, R. Sarkissian and J.-P. Vial
Abstract
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.
Decomposition is an algorithmic device that breaks down computations
into several independent subproblems. It is thus ideally suited to
parallel implementation. To achieve robustness and greater
reliability in the performance of the decomposition algorithm, we
use the Analytic Center Cutting Plane Method (ACCPM) to
handle the master program. We run the algorithm on two different
parallel computing platforms: a network of PC's running under Linux
and 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.
Key words: Decomposition, Parallel Computation, Analytic Center, Cutting Plane Method, Real-Life Problems.