A least-squares minimum-cost network flow algorithm

Balaji Gopalakrishnan (), Seunghyun Kong (), Earl Barnes (), Ellis Johnson () and Joel Sokol ()

Annals of Operations Research, 2011, vol. 186, issue 1, 119-140

Abstract: Node-arc incidence matrices in network flow problems exhibit several special least-squares properties. We show how these properties can be leveraged in a least-squares primal-dual algorithm for solving minimum-cost network flow problems quickly. Computational results show that the performance of an upper-bounded version of the least-squares minimum-cost network flow algorithm with a special dual update operation is comparable to CPLEX Network and Dual Optimizers for solving a wide range of minimum-cost network flow problems. Copyright Springer Science+Business Media, LLC 2011

Keywords: Network flow; Least-squares; Primal-dual (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-011-0858-7 (text/html)
Access to full text is restricted to subscribers.

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:spr:annopr:v:186:y:2011:i:1:p:119-140:10.1007/s10479-011-0858-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-011-0858-7

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().