Chapter 5 Parallel Computing in Network Optimization

Dimitri Bertsekas, David Castañon, Jonathan Eckstein, Stavros Zenios

Research output: Contribution to journalReview article

11 Scopus citations

Abstract

Parallel and vector supercomputers are today considered basic research tools for several scientific and engineering disciplines. The novel architectural features of these computers which differ significantly from the von Neumann model are influencing the design and implementation of algorithms for numerical computation. This chapter discusses parallel architectures and broad issues that relate to the implementation and performance evaluation of parallel algorithms. It also defines the network optimization problems. The topic of parallel computing for linear network optimization problems and nonlinear networks are discussed. The chapter provides brief overview of additional work for multicommodity network flows and stochastic network programs. The general methodological ideas for the design of specific algorithms for each problem class are given. The algorithms that have some potential for parallelism are also discussed. The methodological development is followed by a subsection of parallelization ideas, i.e., specific ways in which each algorithm can be implemented on a parallel computer. Finally, computational results with the parallel implementation of some of the algorithms that have appeared in the literature are summarized and discussed.

Original languageEnglish (US)
Pages (from-to)331-399
Number of pages69
JournalHandbooks in Operations Research and Management Science
Volume7
Issue numberC
DOIs
Publication statusPublished - Jan 1 1995
Externally publishedYes

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Finance
  • Economics and Econometrics
  • Computer Science Applications
  • Management Science and Operations Research

Cite this