×

On solving multi objective set covering problem with imprecise linear fractional objectives. (English) Zbl 1326.90052

Summary: The Set Covering problem is one the of most important NP-complete 0-1 integer programming problems because it serves as a model for many real world problems like the crew scheduling problem, facility location problem, vehicle routing etc. In this paper, an algorithm is suggested to solve a multi objective Set Covering problem with fuzzy linear fractional functionals as the objectives. The algorithm obtains the complete set of efficient cover solutions for this problem. It is based on the cutting plane approach, but employs a more generalized and a much deeper form of the Dantzig cut. The fuzziness in the problem lies in the coefficients of the objective functions. In addition, the ordering between two fuzzy numbers is based on the possibility and necessity indices introduced by D. Dubois and H. Prade [Inf. Sci. 30, 183–224 (1983; Zbl 0569.94031)]. Our aim is to develop a method which provides the decision maker with a fuzzy solution. An illustrative numerical example is elaborated to clarify the theory and the solution algorithm.

MSC:

90C10 Integer programming
90C70 Fuzzy and other nonstochastic uncertainty mathematical programming

Citations:

Zbl 0569.94031
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S.R. Arora, M.C. Puri and Kanti Swarup, The Set Covering Problem with linear fractional functional. Indian J. Pure Appl. Math.8 (1975) 578-588. · Zbl 0434.90093
[2] S.R. Arora and M.C. Puri, Enumeration technique for the Set Covering Problem with a linear fractional functional as its objective function. ZAMM57 (1977) 181-186. · Zbl 0364.90066 · doi:10.1002/zamm.19770570307
[3] S.R. Arora and R.R. Saxena, Cutting plane technique for the multi-objective Set Covering Problem with linear fractional objective functions. IJOMAS14 (1998) 111-122.
[4] S.R. Arora, K. Swarup and M.C. Puri, Cutting plane technique for the Set Covering Problem with linear fractional functional. ZAMM57 (1977) 597-602. · Zbl 0367.90095 · doi:10.1002/zamm.19770571006
[5] M. Bellmore and H.D. Ratliff, Set covering and involutory bases. Manag. Sci.18 (1971) 194-206. · Zbl 0241.90036 · doi:10.1287/mnsc.18.3.194
[6] G.R. Bitran and A.G. Novaes, Linear programming with a fractional objective function. Oper. Res.21 (1973) 22-29. · Zbl 0259.90046 · doi:10.1287/opre.21.1.22
[7] M. Chakraborty and S. Gupta, Fuzzy mathematical programming for multi objective linear fractional programming problem. Fuzzy Sets Syst.125 (2002) 335-342. · Zbl 1014.90085 · doi:10.1016/S0165-0114(01)00060-4
[8] A. Charnes and W.W. Cooper, Programming with linear fractional functionals. Nav. Res. Logist. Q.9 (1962) 181-186. · Zbl 0127.36901 · doi:10.1002/nav.3800090303
[9] E.U. Choo and D.R. Atkins, An interactive algorithm for multicriteria programming. Comput. Oper. Res.7. (1980) 81-87. · doi:10.1016/0305-0548(80)90016-7
[10] D. Dubois and H. Prade, Fuzzy Sets and Systems: Theory and Applications. Academic (1980) 393 p. · Zbl 0444.94049
[11] D. Dubois and H. Prade, Ranking fuzzy numbers in the setting of possibility theory. Inf. Sci.30 (1983) 183-224. · Zbl 0569.94031 · doi:10.1016/0020-0255(83)90025-7
[12] R.S. Garfinkel and G.L. Nemhauser, Integer Programming. A Wiley Inter Science Publication, John Wiley and Sons (1973) 448p.
[13] R. Gupta and R. Malhotra, Multi-criteria integer linear fractional programming problem. Optimization35 (1995) 373-389. · Zbl 0874.90139 · doi:10.1080/02331939508844157
[14] J.R. Isbell and W.H. Marlow, Attrition games. Nav. Res. Logist. Q.3 (1956) 71-93. · Zbl 0122.15405 · doi:10.1002/nav.3800030108
[15] J.S.H. Kornbluth and R.E. Steuer, Multiple objective linear fractional programming. Manag. Sci.27 (1981) 1024-1039. · Zbl 0467.90064 · doi:10.1287/mnsc.27.9.1024
[16] C.E. Lemkin, H.M. Salkin and K. Speilberg, Set Covering by single-branch enumeration with linear-programming subproblems. Oper. Res.19 (1971) 998-1022. · Zbl 0232.90033 · doi:10.1287/opre.19.4.998
[17] D.F. Li and S. Chen, A fuzzy programming approach to fuzzy linear fractional programming with fuzzy coefficients. J. Fuzzy Math.4 (1996) 829-834. · Zbl 0870.90104
[18] M.K. LuhandjulaFuzzy approaches for multiple objective linear fractional optimization. Fuzzy Sets Syst.13 (1984) 11-23.
[19] A. Mehra, S. Chandra and C.R. Bector, Acceptable optimality in linear fractional programming with fuzzy coefficients. Fuzzy Optim. Decis. Making6 (2007) 5-16. · Zbl 1278.90489 · doi:10.1007/s10700-006-0021-0
[20] M. Sakawa, H. Yano and J. Takahashi, Pareto optimality for multiobjective linear fractional programming problems with fuzzy parameters. Inf. Sci.63 (1992) 33-53. · Zbl 0764.90087 · doi:10.1016/0020-0255(92)90061-C
[21] I.M. Stancu-Minasian and B. Pop, On a fuzzy set approach to solving multiple objective linear fractional programming problem. Fuzzy Sets Syst.134 (2003) 397-405. · Zbl 1026.90106 · doi:10.1016/S0165-0114(02)00142-2
[22] K. Swarup, Linear fractional functionals programming. Oper. Res.13 (1965) 1029-1036. · Zbl 0132.13802 · doi:10.1287/opre.13.6.1029
[23] R.R. Saxena and R. Gupta, Linearization technique for solving quadratic fractional set covering, partitioning and packing problems. Int. J. Eng. Soc. Sci.2 (2012) 49-87.
[24] R.R. Saxena and R. Gupta, Enumeration technique for solving linear fractional fuzzy set covering problem. Int. J. Pure Appl. Math.84 (2013) 477-496. · doi:10.12732/ijpam.v84i5.3
[25] R.R. Saxena and R. Gupta, Enumeration technique for solving linear fuzzy set covering problem. Int. J. Pure Appl. Math.85 (2013) 635-651. · doi:10.12732/ijpam.v85i4.2
[26] M. Upmanyu and R.R. Saxena, Multi objective linear set covering problem with imprecise objective functions. Int. J. Res in IT, Management and Engineering2 (2012) 28-42.
[27] V. Verma, H.C. Bakshi and M.C. Puri, Ranking in integer linear fractional programming problems. ZOR- Methods and Models of Operations Research.34 (1990) 325-334. · Zbl 0721.90072 · doi:10.1007/BF01416224
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.