Parallel primal-dual methods for the minimum cost flow problem

Dimitri P. Bertsekas, David A. Castañon

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


In this paper we discuss the parallel asynchronous implementation of the classical primaldual method for solving the linear minimum cost network flow problem. Multiple augmentations and price rises are simultaneously attempted starting from several nodes with possibly outdated price and flow information. The results are then merged asynchronously subject to rather weak compatibility conditions. We show that this algorithm is valid, terminating finitely to an optimal solution. We also present computational results using an Encore MULTIMAX that illustrate the speedup that can be obtained by parallel implementation.

Original languageEnglish (US)
Pages (from-to)317-336
Number of pages20
JournalComputational Optimization and Applications
Issue number4
StatePublished - Dec 1993
Externally publishedYes


  • Optimization
  • network programming
  • primal-dual
  • transshipment

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Parallel primal-dual methods for the minimum cost flow problem'. Together they form a unique fingerprint.

Cite this