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

J. Gondzio, R. Sarkissian, J. P. Vial

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)5-29
Number of pages25
JournalComputational optimization and applications
Volume19
Issue number1
DOIs
Publication statusPublished - 1 Apr 2001

Keywords

  • Analytic center
  • Cutting plane method
  • Decomposition
  • Parallel computation
  • Real-life problems

Fingerprint

Dive into the research topics of 'Parallel implementation of a central decomposition method for solving large-scale planning problems'. Together they form a unique fingerprint.

Cite this