×

Fractional multi-commodity flow problem: duality and optimality conditions. (English) Zbl 1427.90240

Summary: 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 [S. S. Chadha and V. Chadha, CEJOR, Cent. Eur. J. Oper. Res. 15, No. 2, 119–125 (2007; Zbl 1151.90051)]. 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.

MSC:

90C27 Combinatorial optimization
90C32 Fractional programming
90C46 Optimality conditions and duality in mathematical programming

Citations:

Zbl 1151.90051
Full Text: DOI

References:

[1] Chadha, S. S.; Chadha, V., Linear fractional programming and duality, Cent. Eur. J. Oper. Res., 15, 119-125 (2007) · Zbl 1151.90051
[2] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows: Theory and Applications (1993), Prentice-Hall: Prentice-Hall Englewood cliffs · Zbl 1201.90001
[3] Salehi Fathabadi, H.; Khodayifar, S.; Raayatpanah, M. A., Minimum flow problem on network flows with time-varying bounds, Appl. Math. Model., 36, 4414-4421 (2012) · Zbl 1252.90013
[4] Jimenez, F.; Verdegay, J. L., Solving fuzzy solid transportation problems by an evolutionary algorithm based parametric approach, Eur. J. Oper. Res., 117, 485-510 (1999) · Zbl 0937.90067
[5] Ghatee, M.; Hashemi, S. M., Some concepts of the fuzzy multicommodity flow problem and their application in fuzzy network design, Math. Comput. Model., 49, 1030-1043 (2009) · Zbl 1165.90355
[6] Schaible, S., Fractional programming, (Horst, R.; Pardalos, P. M., Handbook of Global Optimization (1995), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, Boston, London), 495-608 · Zbl 0832.90115
[8] Bazaraa, M. S.; Sherali, H. D.; Shetty, C. M., Nonlinear Programming: Theory and Algorithms (2006), John Wiley & Sons · Zbl 1140.90040
[10] Xu, C.; Xu, X. M.; Wang, H. F., The fractional minimal cost flow problem on network, Optim. Lett., 5, 307-317 (2011) · Zbl 1242.90254
[11] Sherali, H. D., On a fractional minimal cost flow problem on networks, Optim. Lett., 6, 1945-1949 (2012) · Zbl 1258.90078
[12] Charnes, A.; Cooper, W. W., Programming with linear fractional functionals, Naval Res. Logistics Quart., 9, 181-196 (1962) · Zbl 0127.36901
[13] Schaible, S., Duality in fractional programming: a unified approach, Oper. Res., 24, 452-461 (1976) · Zbl 0348.90120
[14] Bazaraa, M. S.; Jarvis, J. J.; Sherali, H. D., Linear Programming and Network Flows (1990), John Wiley & Sons · Zbl 0722.90042
[15] Stephen, J. W., Primal-dual interior-point methods (1997), SIAM · Zbl 0863.65031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.