Fractional multi-commodity flow problem: Duality and optimality conditions |
| |
Institution: | Department of Computer Science, Amirkabir University of Technology, No. 424, Hafez Avenue, Tehran 15875-4413, Iran;Intelligent Transportation Systems Research Institute, Amirkabir University of Technology, Tehran, Iran |
| |
Abstract: | This paper deals with multi-commodity flow problem with fractional objective function. The optimality conditions and the duality concepts of this problem are given. For this aim, the fractional linear programming formulation of this problem is considered and the weak duality, the strong direct duality and the weak complementary slackness theorems are proved applying the traditional duality theory of linear programming problems which is different from same results in Chadha and Chadha (2007) 1]. In addition, a strong (strict) complementary slackness theorem is derived which is firstly presented based on the best of our knowledge. These theorems are transformed in order to find the new reduced costs for fractional multi-commodity flow problem. These parameters can be used to construct some algorithms for considered multi-commodity flow problem in a direct manner. Throughout the paper, the boundedness of the primal feasible set is reduced to a weaker assumption about solvability of primal problem which is another contribution of this paper. Finally, a real world application of the fractional multi-commodity flow problem is presented. |
| |
Keywords: | Combinatorial optimization Fractional programming Duality Strong complementary slackness Multi-commodity flow problem |
本文献已被 ScienceDirect 等数据库收录! |
|