Cover Image

On network flow problems with convex cost

Minimum cost flow (MCF) problem is a typical example of network flow problems, for which an additional constraint of cost is added to each flow. Conventional MCF problems consider the cost constraints as linear functions of flow. In this paper, we extend the MCF problem to cover cost functions as st...

Full description

Saved in:
Bibliographic Details
Main Authors: Nguyen, V.A., Tan, Y. P.
Format: Article
Language:English
Published: Universiti Utara Malaysia 2004
Subjects:
QA75 Electronic computers. Computer science
Online Access:http://repo.uum.edu.my/1042/1/V._A._Nguyen.pdf
http://repo.uum.edu.my/1042/
http://jict.uum.edu.my
Tags: Add Tag
No Tags, Be the first to tag this record!
id my.uum.repo.1042
record_format eprints
spelling my.uum.repo.10422010-09-05T06:06:59Z http://repo.uum.edu.my/1042/ On network flow problems with convex cost Nguyen, V.A. Tan, Y. P. QA75 Electronic computers. Computer science Minimum cost flow (MCF) problem is a typical example of network flow problems, for which an additional constraint of cost is added to each flow. Conventional MCF problems consider the cost constraints as linear functions of flow. In this paper, we extend the MCF problem to cover cost functions as strictly convex and differentiable, and refer to the problem as convex cost flow problem. To address this problem, we derive the optimality conditions for minimising convex and differentiable cost functions, and devise an algorithm based on the primal-dual algorithm commonly used in linear programming. The proposed algorithm minimises the total cost of flow by incrementing the network flow along augmenting paths of minimum cost. Simulation results are provided to demonstrate the efficacy of the proposed algorithm. Universiti Utara Malaysia 2004 Article PeerReviewed application/pdf en http://repo.uum.edu.my/1042/1/V._A._Nguyen.pdf Nguyen, V.A. and Tan, Y. P. (2004) On network flow problems with convex cost. Journal of ICT, 3 (1). pp. 33-51. ISSN 1675-414X http://jict.uum.edu.my
institution Universiti Utara Malaysia
building UUM Library
collection Institutional Repository
continent Asia
country Malaysia
content_provider Universiti Utara Malaysia
content_source UUM Institutionali Repository
url_provider http://repo.uum.edu.my/
language English
topic QA75 Electronic computers. Computer science
spellingShingle QA75 Electronic computers. Computer science
Nguyen, V.A.
Tan, Y. P.
On network flow problems with convex cost
description Minimum cost flow (MCF) problem is a typical example of network flow problems, for which an additional constraint of cost is added to each flow. Conventional MCF problems consider the cost constraints as linear functions of flow. In this paper, we extend the MCF problem to cover cost functions as strictly convex and differentiable, and refer to the problem as convex cost flow problem. To address this problem, we derive the optimality conditions for minimising convex and differentiable cost functions, and devise an algorithm based on the primal-dual algorithm commonly used in linear programming. The proposed algorithm minimises the total cost of flow by incrementing the network flow along augmenting paths of minimum cost. Simulation results are provided to demonstrate the efficacy of the proposed algorithm.
format Article
author Nguyen, V.A.
Tan, Y. P.
author_facet Nguyen, V.A.
Tan, Y. P.
author_sort Nguyen, V.A.
title On network flow problems with convex cost
title_short On network flow problems with convex cost
title_full On network flow problems with convex cost
title_fullStr On network flow problems with convex cost
title_full_unstemmed On network flow problems with convex cost
title_sort on network flow problems with convex cost
publisher Universiti Utara Malaysia
publishDate 2004
url http://repo.uum.edu.my/1042/1/V._A._Nguyen.pdf
http://repo.uum.edu.my/1042/
http://jict.uum.edu.my
_version_ 1644277911442685952
score 13.211869

Similar Items