Chapter 5 Parallel Computing in Network Optimization

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

Research output: Contribution to journalReview article

10 Citations (Scopus)

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
StatePublished - Jan 1 1995

Fingerprint

Parallel processing systems
Nonlinear networks
Linear networks
Parallel architectures
Supercomputers
Parallel algorithms
Parallel computing
Network optimization

All Science Journal Classification (ASJC) codes

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

Cite this

Bertsekas, Dimitri ; Castañon, David ; Eckstein, Jonathan ; Zenios, Stavros. / Chapter 5 Parallel Computing in Network Optimization. In: Handbooks in Operations Research and Management Science. 1995 ; Vol. 7, No. C. pp. 331-399.
@article{f97e9a7b50984a85811d1c17de108930,
title = "Chapter 5 Parallel Computing in Network Optimization",
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.",
author = "Dimitri Bertsekas and David Casta{\~n}on and Jonathan Eckstein and Stavros Zenios",
year = "1995",
month = "1",
day = "1",
doi = "10.1016/S0927-0507(05)80122-7",
language = "English (US)",
volume = "7",
pages = "331--399",
journal = "Handbooks in Operations Research and Management Science",
issn = "0927-0507",
publisher = "North-Holland Publ Co",
number = "C",

}

Chapter 5 Parallel Computing in Network Optimization. / Bertsekas, Dimitri; Castañon, David; Eckstein, Jonathan; Zenios, Stavros.

In: Handbooks in Operations Research and Management Science, Vol. 7, No. C, 01.01.1995, p. 331-399.

Research output: Contribution to journalReview article

TY - JOUR

T1 - Chapter 5 Parallel Computing in Network Optimization

AU - Bertsekas, Dimitri

AU - Castañon, David

AU - Eckstein, Jonathan

AU - Zenios, Stavros

PY - 1995/1/1

Y1 - 1995/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=1542326866&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1542326866&partnerID=8YFLogxK

U2 - 10.1016/S0927-0507(05)80122-7

DO - 10.1016/S0927-0507(05)80122-7

M3 - Review article

AN - SCOPUS:1542326866

VL - 7

SP - 331

EP - 399

JO - Handbooks in Operations Research and Management Science

JF - Handbooks in Operations Research and Management Science

SN - 0927-0507

IS - C

ER -