Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
International Journal of Machine Learning and Cybernetics
Published in: International Journal of Machine Learning and Cybernetics 3/2017

03-05-2015 | Original Article

A rough set method for the unicost set covering problem

Authors: Qingyuan Xu, Anhui Tan, Yaojin Lin

Published in: International Journal of Machine Learning and Cybernetics | Issue 3/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, we aim to provide a rough set method to deal with a class of set covering problem called the unicost set covering problem, which is a well-known problem in binary optimization. Firstly, by constructing a Multi-Relation Granular Computing (GrC) model of a given unicost set covering problem, the problem can be equivalently converted to the knowledge reduction problem in rough set theory. Thus, various kinds of efficient knowledge reduction methods in rough set theory can be used to solve the unicost set covering problem. Secondly, a commonly used reduction algorithm based on information entropy is proposed to compute a local minimum of the unicost set covering problem. Finally, the feasibility and efficiency of the proposed algorithm is examined by an example.
previous article Improved discrete mapping differential evolution for multi-unmanned aerial vehicles cooperative multi-targets assignment under unified model
next article Adaptive semi-supervised dimensionality reduction based on pairwise constraints weighting and graph optimizing

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Show more products
Literature
1.
Balas E (1982) Class of location, distribution and scheduling problems: modeling and solution methods. Carnegie Mellon University, Design Research Center, New YorkMATH
2.
3.
Bilal N, Galinier P, Guibault F (2013) A new formulation of the set covering problem for metaheuristic approaches. Hindawi Publishing Corporation, ISRN Operations Research, Volume 2013, Article ID 203032, p 10. doi:10.​1155/​2013/​203032
4.
5.
Chen DG, Zhao SY, Zhang L et al (2012) Sample pair selection for attribute reduction with rough set. IEEE Transac Know Data Eng 24(11):2080–2093CrossRef
6.
Deng TQ, Yang CD, Wang XF (2012) A reduct derived from feature selection. Pattern Recogn Lett 33(12):1638–1646CrossRef
7.
Grzymala-Busse JW (1992) LERS-a system for learning from examples based on rough sets. In: Slowinski R (ed) Intelligent Decision Support: Handbook of Applications and Advances of the Rough Set Theory, Kluwer Academic Publishers, pp 3–18
8.
Gu SM, Wu WZ (2013) On knowledge acquisition in multi-scale decision systems. Int J Mach Learn Cybernet 4(5):477–486CrossRef
9.
Hu QH, Zhang L, Zhang D et al (2011) Measuring relevance between discrete and continuous features based on neighborhood mutual information. Expert Syst Appl 38(9):10737–10750CrossRef
10.
Hu XH, Cercone N (1995) Learning in relational databases: a rough set approach. Comput Intell 11(2):323–338CrossRef
11.
Johnson DS, Garey MR (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman & Company, NewYorkMATH
12.
Lan G, DePuy GW, Whitehouse GE (2007) An effective and simple heuristic for the set covering problem. Eur J Oper Res 176(3):1387–1403MathSciNetCrossRefMATH
13.
14.
Liang JY, Chin KS, Dang CY et al (2002) A new method for measuring uncertainty and fuzziness in rough set theory. Int J General Syst 31(4):331–342MathSciNetCrossRefMATH
15.
Liang JY, Qian YH (2008) Information granules and entropy theory in information systems. Sci China Ser F Inform Sci 51(10):1427–1444MathSciNetCrossRefMATH
16.
Liang JY, Shi ZZ (2004) The information entropy, rough entropy and knowledge granulation in rough set theory. Int J Uncertain Fuzziness Knowl Based Syst 12(1):37–46MathSciNetCrossRefMATH
17.
Lin TY (1988) Neighborhood systems and relational database. In: Proceedings of CSC’88
18.
Lin TY (1992) Topological and fuzzy rough sets. In: Slowinski R (ed) Intelligent Decision Support: Handbook of Applications and Advances of the Rough Sets Theory. Kluwer Academic Publishers, Boston, pp 287–304CrossRef
19.
Lin TY (1989) Neighborhood systems and approximation in relational databases and knowledge bases. Poster Session. In: Proceedings of the Fourth International Symposium on ethodologies of Intelligent Systems, pp 75–86
20.
Lin TY (2009) Granular computing: practices, theories, and future directions. Springer, Encyclopedia on Complexity of Systems Science, pp 4339–4355
21.
X. liu, Y.H. Qian, J.Y. Liang, A rule-extraction framework under multigranulation rough sets, Int J Mach Learn Cybernet 5 (2) (2014) 319–326
22.
Miao DQ, Zhao Y, Yao YY et al (2009) Relative reducts in consistent and inconsistent decision tables of the pawlak rough set model. Inform Sci 179(24):4140–4150MathSciNetCrossRefMATH
23.
Min F, He HP, Qian YH, Zhu W (2011) Test-cost-sensitive attribute reduction. Inform Sci 181(22):4928–4942CrossRef
24.
25.
26.
Pawlak Z (1991) Rough sets: theoretical aspects of reasoning about data. Kluwer Academic Publishing, DordrechtCrossRefMATH
27.
Peters JF, Skowron A, Suraj Z (2000) An application of rough set methods in control design. Fundam Inform 43(1):269–290MathSciNetMATH
28.
Qian YH, Liang JY (2008) Combination entropy and combination granulation in rough set theory. Int J Uncertain Fuzziness Knowl Based Syst 16(2):179–193MathSciNetCrossRefMATH
29.
Qian YH, Liang JY, Pedrycz W, Dang CY (2010) Positive approximation: an accelerator for attribute reduction in rough set theory. Artif Intell 174(9–10):597–618MathSciNetCrossRefMATH
30.
Skowron A, Rauszer C (1992) The discernibility matrices and functions in information systems. In: Slowinski R (ed) Intelligent Decision Support. Handbook of Applications and Advances of the Rough Sets Theory, Kluwer, pp 331–362CrossRef
31.
Slezak D (1996) Approximate reducts in decision tables, Research report. Institute of Computer Science, Warsaw University of Technology
32.
33.
Steiglitz K, Papadimitriou CH (1982) Combinatorial optimization: algorithms and complexity. Prentice-Hall, Englewood CliffsMATH
34.
Sun YF, Wang ZT (1994) The genetic algorithm for 0–1 programming with linear constraints. In: Fogel DB (ed) Proceedings of the 1st ICEC94. Orlando, FL, pp 559–564
35.
Sundar S, Singh A (2012) A hybrid heuristic for the set covering problem. Oper Res 12(3):345–365MATH
36.
Swiniarski RW, Skowron A (2003) Rough set methods in feature selection and recognition. Pattern Recogn Lett 24(6):833–849CrossRefMATH
37.
Synak P, Bazan JG, Skowron A, Peters JF (2005) Spatio-temporal approximate reasoning over complex objects. Fundam Inform 67(1):249–269MathSciNetMATH
38.
39.
40.
Toregas C, Swain R, ReVelle C, Bergman L (1971) The location of emergency service facilities. Oper Res 19(6):1363–1373CrossRefMATH
41.
Wang GY, Yu H, Yang DC (2002) Decision table reduction based on conditional information entropy. Chinese J Comput 25(7):759–766MathSciNet
42.
Wang GY, Zhao J, An JJ, Wu Y (2005) A comparative study of algebra viewpoint and information viewpoint in attribute reduction. Fundam Inform 68(3):289–301MathSciNetMATH
43.
Wang J, Wang J (2001) Reduction algorithms based on discernibility matrix: the ordered attributes method. J Comput Sci Technol 16(6):489–504MathSciNetCrossRefMATH
44.
Wang XZ, Li CG, A new definition of sensitivity for RBFNN and its applications to feature reduction, Advances in Neural NetworksCISNN, (2005) Springer. Berlin Heidelberg 2005:81–86
45.
Wong SKM, Ziarko W (1985) On optimal decision rules in decision tables. Bull Polish Acad Sci 33:693–696MathSciNetMATH
46.
Wu SX, Li MQ, Huang WT, Liu SF (2004) An improved heuristic algorithm of attribute reduction in rough set. J Syst Sci Inform 2(3):557–562
47.
Wu WZ, Zhang M, Li HZ, Mi JS (2005) Knowledge reduction in random information systems via dempster-shafer theory of evidence. Inform Sci 174(3):143–164MathSciNetCrossRefMATH
48.
Yang XB, Song XN, Chen ZH, Yang JY (2012) On multigranulation rough sets in incomplete information system. Int J Machine Learn Cybernet 3(3):223–232CrossRef
49.
Yao YY (1998) Relational interpretations of neighborhood operators and rough set approximation operators. Inform Sci 111(1):239–259MathSciNetCrossRefMATH
50.
51.
Metadata
Title
A rough set method for the unicost set covering problem
Authors
Qingyuan Xu
Anhui Tan
Yaojin Lin
Publication date
03-05-2015
Publisher
Springer Berlin Heidelberg
Published in
International Journal of Machine Learning and Cybernetics / Issue 3/2017
Print ISSN: 1868-8071
Electronic ISSN: 1868-808X
DOI
https://doi.org/10.1007/s13042-015-0365-2

Other articles of this Issue 3/2017

International Journal of Machine Learning and Cybernetics 3/2017 Go to the issue

Original Article

An efficient modified differential evolution algorithm for solving constrained non-linear integer and mixed-integer global optimization problems

Original Article

Label denoising based on Bayesian aggregation

Original Article

A multi-attribute decision-making method with prioritization relationship and dual hesitant fuzzy decision information

Original Article

The classification of imbalanced large data sets based on MapReduce and ensemble of ELM classifiers

Original Article

An improved artificial bee colony algorithm for solving constrained optimization problems

Original Article

An optimal learning-based controller derived from Hamiltonian function combined with a cellular searching strategy for automotive coldstart emissions