On solving multi objective Set Covering Problem with imprecise linear fractional objectives
Upmanyu, Mudita1 ; Saxena, Ratnesh R2
1 Department of Mathematics, University of Delhi, Delhi, India
2 Associate Professor, Department of Mathematics, Deen Dayal Upadhyaya College, University of Delhi, Delhi, India
RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 3, pp. 495-510.

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 Dubois and Prade [Ranking fuzzy numbers in the setting of possibility theory. Inf. Sci. 30 (1983) 183–224.]. 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.

DOI : 10.1051/ro/2014045
Classification : 90C10, 90C70
Mots-clés : Set covering Problem, multi objective linear fractional programming, fuzzy mathematical programming, fuzzy objective function
Upmanyu, Mudita 1 ; Saxena, Ratnesh R 2

1 Department of Mathematics, University of Delhi, Delhi, India
2 Associate Professor, Department of Mathematics, Deen Dayal Upadhyaya College, University of Delhi, Delhi, India 
@article{RO_2015__49_3_495_0,
     author = {Upmanyu, Mudita and Saxena, Ratnesh R},
     title = {On solving multi objective {Set} {Covering} {Problem} with imprecise linear fractional objectives},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {495--510},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {3},
     year = {2015},
     doi = {10.1051/ro/2014045},
     mrnumber = {3349131},
     zbl = {1326.90052},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2014045/}
}
TY  - JOUR
AU  - Upmanyu, Mudita
AU  - Saxena, Ratnesh R
TI  - On solving multi objective Set Covering Problem with imprecise linear fractional objectives
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2015
SP  - 495
EP  - 510
VL  - 49
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2014045/
DO  - 10.1051/ro/2014045
LA  - en
ID  - RO_2015__49_3_495_0
ER  - 
%0 Journal Article
%A Upmanyu, Mudita
%A Saxena, Ratnesh R
%T On solving multi objective Set Covering Problem with imprecise linear fractional objectives
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2015
%P 495-510
%V 49
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2014045/
%R 10.1051/ro/2014045
%G en
%F RO_2015__49_3_495_0
Upmanyu, Mudita; Saxena, Ratnesh R. On solving multi objective Set Covering Problem with imprecise linear fractional objectives. RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 3, pp. 495-510. doi : 10.1051/ro/2014045. http://www.numdam.org/articles/10.1051/ro/2014045/

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. | MR | Zbl

S.R. Arora and M.C. Puri, Enumeration technique for the Set Covering Problem with a linear fractional functional as its objective function. ZAMM 57 (1977) 181–186. | DOI | MR | Zbl

S.R. Arora and R.R. Saxena, Cutting plane technique for the multi-objective Set Covering Problem with linear fractional objective functions. IJOMAS 14 (1998) 111–122.

S.R. Arora, K. Swarup and M.C. Puri, Cutting plane technique for the Set Covering Problem with linear fractional functional. ZAMM 57 (1977) 597–602. | DOI | MR | Zbl

M. Bellmore and H.D. Ratliff, Set covering and involutory bases. Manag. Sci. 18 (1971) 194–206. | DOI | MR | Zbl

G.R. Bitran and A.G. Novaes, Linear programming with a fractional objective function. Oper. Res. 21 (1973) 22–29. | DOI | MR | Zbl

M. Chakraborty and S. Gupta, Fuzzy mathematical programming for multi objective linear fractional programming problem. Fuzzy Sets Syst. 125 (2002) 335–342. | DOI | MR | Zbl

A. Charnes and W.W. Cooper, Programming with linear fractional functionals. Nav. Res. Logist. Q. 9 (1962) 181–186. | DOI | MR | Zbl

E.U. Choo and D.R. Atkins, An interactive algorithm for multicriteria programming. Comput. Oper. Res. 7. (1980) 81–87. | DOI

D. Dubois and H. Prade, Fuzzy Sets and Systems: Theory and Applications. Academic (1980) 393 p. | MR | Zbl

D. Dubois and H. Prade, Ranking fuzzy numbers in the setting of possibility theory. Inf. Sci. 30 (1983) 183–224. | DOI | MR | Zbl

R.S. Garfinkel and G.L. Nemhauser, Integer Programming. A Wiley Inter Science Publication, John Wiley and Sons (1973) 448p. | MR | Zbl

R. Gupta and R. Malhotra, Multi-criteria integer linear fractional programming problem. Optimization 35 (1995) 373–389. | DOI | MR | Zbl

J.R. Isbell and W.H. Marlow, Attrition games. Nav. Res. Logist. Q. 3 (1956) 71–93. | DOI | MR | Zbl

J.S.H. Kornbluth and R.E. Steuer, Multiple objective linear fractional programming. Manag. Sci. 27 (1981) 1024–1039. | DOI | Zbl

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. | DOI | MR | Zbl

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. | MR | Zbl

M.K. Luhandjula Fuzzy approaches for multiple objective linear fractional optimization. Fuzzy Sets Syst. 13 (1984) 11–23. | MR | Zbl

A. Mehra, S. Chandra and C.R. Bector, Acceptable optimality in linear fractional programming with fuzzy coefficients. Fuzzy Optim. Decis. Making 6 (2007) 5–16. | DOI | MR | Zbl

M. Sakawa, H. Yano and J. Takahashi, Pareto optimality for multiobjective linear fractional programming problems with fuzzy parameters. Inf. Sci. 63 (1992) 33–53. | DOI | MR | Zbl

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. | DOI | MR | Zbl

K. Swarup, Linear fractional functionals programming. Oper. Res. 13 (1965) 1029–1036. | DOI | Zbl

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.

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

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

M. Upmanyu and R.R. Saxena, Multi objective linear set covering problem with imprecise objective functions. Int. J. Res in IT, Management and Engineering 2 (2012) 28–42.

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. | DOI | MR | Zbl

Cité par Sources :