Chapter 5 Parallel computing in network optimization
Dimitri P. Bertsekas, David A. Castañón, Jonathan Eckstein, Stavros A. Zenios · Handbooks in operations research and management science · 1995
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.