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...
保存先:
| 主要な著者: | , |
|---|---|
| フォーマット: | 論文 |
| 言語: | English |
| 出版事項: |
Universiti Utara Malaysia
2004
|
| 主題: | |
| オンライン･アクセス: | http://repo.uum.edu.my/1042/1/V._A._Nguyen.pdf http://repo.uum.edu.my/1042/ http://jict.uum.edu.my |
| タグ: |
タグ追加
タグなし, このレコードへの初めてのタグを付けませんか!
|
| 要約: | 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. |
|---|