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

Preview

PDF Download (4MB) | Preview

Abstract

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.

Item Type:	Article
Uncontrolled Keywords:	Minimum cost flow problem, convex cost functions, primal-dual, algorithm, network flow
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions:	UNSPECIFIED
Depositing User:	Mrs. Norazmilah Yaakub
Date Deposited:	05 Sep 2010 04:57
Last Modified:	05 Sep 2010 06:06
URI:	https://repo.uum.edu.my/id/eprint/1042

Actions (login required)

View Item