Parallel primal-dual methods for the minimum cost flow problem

DOI10.1007/BF01299544MaRDI QIDQ1315451zbMATH OpenOpenAlexFDO

Authors Dimitri P. Bertsekas, David A. Castanon

Publication date 1993

Published in Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01299544

zbMATH Keywords

asynchronous implementationminimum-cost capacitated flowparallel implementationpath-augmentation algorithmprimal-dual method

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Deterministic network models in operations research (90B10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Programming involving graphs or networks (90C35)

Review text

The subject of this paper is an asynchronous implementation of the classical path-augmentation algorithm for minimum-cost capacitated flow problem. The technique allows multiple parallel flow augmentation computations with potentially outdated data and the authors show that the resulting algorithm converges in a finite number of iterations subject to mild conditions. Computation times are reported for two NETGEN problems indicating reductions of the computation times of up to 20\% with respect to a synchronous parallel implementation of the algorithm.

Recommendations

• Efficient parallel algorithms for the minimum cost flow problem
• Parallel algorithms for solving the convex minimum cost flow problem
• scientific article; zbMATH DE number 870979
• A parallel asynchronous implementation of the \(\epsilon\)-relaxation method for the linear minimum cost flow problem
• Data-level parallel solution of min-cost network flow problems using \(\varepsilon\)-relaxations

Cites work

• A parallel shortest augmenting path algorithm for the assignment problem
• A unified framework for primal-dual methods in minimum cost network flow problems
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 3961334 (Why is no real title available?)
• scientific article; zbMATH DE number 53116 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 3231710 (Why is no real title available?)
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• Parallel synchronous and asynchronous implementations of the auction algorithm
• Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems

Cited in

(7)

• Dual coordinate step methods for linear network flow problems
• Efficient parallel algorithms for the minimum cost flow problem
• A parallel asynchronous implementation of the \(\epsilon\)-relaxation method for the linear minimum cost flow problem
• Sequential and parallel algorithms for minimum flows.
• scientific article; zbMATH DE number 870979 (Why is no real title available?)
• Parallel algorithms for the maximum flow problem with minimum lot sizes
• Parallel algorithms for solving the convex minimum cost flow problem

Describes a project that uses

Uses Software

• NETGEN
• RELAX4

This page was built for publication: Parallel primal-dual methods for the minimum cost flow problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1315451)