Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems

Dimitri P. Bertsekas and Paul Tseng
Additional contact information
Dimitri P. Bertsekas: Massachusetts Institute of Technology, Cambridge, Massachusetts
Paul Tseng: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1988, vol. 36, issue 1, 93-114

Abstract: We propose a new class of algorithms for linear cost network flow problems with and without gains. These algorithms are based on iterative improvement of a dual cost and operate in a manner that is reminiscent of coordinate ascent and Gauss-Seidel relaxation methods. We compare our coded implementations of these methods with mature state-of-the-art primal simplex and primal-dual codes, and find them to be several times faster on standard benchmark problems, and faster by an order of magnitude on large, randomly generated problems. Our experiments indicate that the speedup factor increases with problem dimension.

Keywords: 484 optimization of single commodity network flows; 643 algorithms for linear network optimization (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.36.1.93 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:36:y:1988:i:1:p:93-114

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().