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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Universiti Utara Malaysia
2004
|
| Subjects: | |
| 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!
|
| Summary: | 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. |
|---|