An Efficient Algorithm for Solving Minimum Cost Flow Problem with Complementarity Slack Conditions

Yongwen Hu, Xiao Zhao, Jing Liu, Binyuan Liang and Chao Ma

Mathematical Problems in Engineering, 2020, vol. 2020, 1-5

Abstract:

This paper presents an algorithm for solving a minimum cost flow (MCF) problem with a dual approach. The algorithm holds the complementary slackness at each iteration and finds an augmenting path by updating node potential iteratively. Then, flow can be augmented at the original network. In contrast to other popular algorithms, the presented algorithm does not find a residual network, nor find a shortest path. Furthermore, our algorithm holds information of node potential at each iteration, and we update node potential within finite iterations for expanding the admissible network. The validity of our algorithm is given. Numerical experiments show that our algorithm is an efficient algorithm for the MCF problem, especially for the network with a small interval of cost of per unit flow.

Date: 2020
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2020/2439265.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2020/2439265.xml (text/xml)

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:hin:jnlmpe:2439265

DOI: 10.1155/2020/2439265

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().