A decision table reduction－based approximate method for set covering problem
Tao Yuzhi1，2，Zhao Shimei1，2，Tan Anhui1，2*
Author information+
{{custom_zuoZheDiZhi}}
About authors:
1.School of Mathematics，Physics and Information Science，Zhejiang Ocean University，Zhoushan，316022，China；
2．Key Laboratory of Oceanographic Big Data Mining & Application of Zhejiang Province，Zhoushan，316022，China
{{custom_authorNodes}}
{{custom_bio.content}}
{{custom_bio.content}}
{{custom_authorNodes}}
Collapse
History+
Published
2018-04-30
Abstract
The set covering problem and the decision table reduction problem are important research subjects in the fields of optimization and information processing，respectively. However，from the perspective of many research achievements，scholars are mostly studying them independently and have not connected them together. In this paper，by analyzing the solution structures of the set covering problem and the decision table reduction problem from the view point of Boolean operations，we study their connections and associate them together. First，we represent a set covering problem by using a Boolean matrix. Then，by classifying the sets in the set covering problem with a decision attribute，a decision information table is further induced，where the Boolean matrix constitutes the conditional attribute values. Second，by examining the relationship between the discernibility sets of a decision table and a set covering，we point out that the sub－optimal solution of the set covering problem is a reduct of the decision table，i.e.，solving the set covering problem is equivalent to solving the attribute reduction problem of the decision table. Then，the conditional entropy of decision tables is employed to measure the relative significance of a set with respect to a collection of sets in the set covering problem，and a conditional entropy－based reduction algorithm of decision tables is introduced to solve the set covering problem. A practical example is used to outline the efficiency and effectiveness of the proposed method. In the end，the new algorithm is compared with several traditional set covering algorithms. The experimental results show that the new algorithm has certain advantages in finding satisfactory solutions.
Tao Yuzhi1，2，Zhao Shimei1，2，Tan Anhui1，2*.
A decision table reduction－based approximate method for set covering problem[J]. Journal of Nanjing University(Natural Sciences), 2018, 54(4): 821
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
References
[1] Pawlak Z. Rough sets. International Journal of Computer & Information Sciences，1982，11(5)：341－356.
[2] 张文修，吴伟志，梁吉业等. 粗糙集理论与方法. 北京：科学出版社，2001，224.
[3] 顾沈明，万雅虹，吴伟志等. 多粒度决策系统的局部最优粒度选择. 南京大学学报(自然科学)，2016，52(2)：280－288.(Gu S M，Wan Y H，Wu W Z，et al. Local optimal granularity selections in multi－granular decision systems. Journal of Nanjing University(Natural Sciences)，2016，52(2)：280－288.)
[4] 胡 谦，米据生，李磊军. 多粒度模糊粗糙近似算子的信任结构与属性约简. 山东大学学报(理学版)，2017，52(7)：30－36.(Hu Q，Mi J S，Li L J. The fuzzy belief structure and attribute reduction based on multi－granulation fuzzy rough operators. Journal of Shandong University(Natural Science)，2017，52(7)：30－36.)
[5] Skowron A，Rauszer C. The discernibility matrices and functions in information systems ∥ Sowiński R. Intelligent Decision Support. Springer Berlin Heidelberg，1992：331－362.
[6] Qian Y H，Liang J Y，Pedrycz W，et al. Positive approximation：An accelerator for attribute reduction in rough set theory. Artificial Intelligence，2010，174(9－10)：597－618.
[7] Liang J Y，Shi Z Z. The information entropy，rough entropy and knowledge granulation in rough set theory. International Journal of Uncertainty，Fuzziness and Knowledge－Based System，2004，12(1)：37－46.
[8] Yao Y Y，Zhao Y. Discernibility matrix simplification for constructing attribute reducts. Information Sciences，2009，179(7)：867－882.
[9] Fomin F V，Kratsch D. Exact exponential algorithms. Berlin：Springer，2010.
[10] Beasley J E，Chu P C. A genetic algorithm for the set covering problem. European Journal of Operational Research，1996，94(2)：392－404.
[11] Aickelin U. An indirect genetic algorithm for set covering problems. Journal of the Operational Research Society，2002，53(10)：1118－1126.
[12] S ＇lzak D. On generalized decision functions：reducts，networks and ensembles ∥ Yao Y Y，Hu Q H，Yu H，et al. Rough Sets，Fuzzy Sets，Data Mining，and Granular Computing. Springer Berlin Heidelberg，2015：13－23.
[13] 胡琳琳，宁爱兵，黄 飞等. 加权集合覆盖问题的加权分治算法. 小型微型计算机系统，2016，37(5)：987－991.(Hu L L，Ning A B，Huang F，et al. Measure and conquer algorithm for minimum weighted set covering problem. Journal of Chinese Computer Systems，2016，37(5)：987－991.)
[14] Aguilera N E，Katz R D，Tolomei P B. Vertex adjacencies in the set covering polyhedron. Discrete Applied Mathematics，2017，218：40－56.
[15] 谭安辉，李进金，陈锦坤等. 图支配集问题的粗糙集属性约简方法. 模式识别与人工智能，2015，28(6)：507－512.(Tan A H，Li J J，Chen J K，et al. An attribute reduction method based on rough sets for dominating sets of graph. Pattern Recognition and Artificial Intelligence，2015，28(6)：507－512.)
[16] 陈彩云，李治国. 关于属性约简和集合覆盖问题的探讨. 计算机工程与应用，2004(2)：44－46，84.(Chen C Y，Li Z G. A study of reduction of attributes and set covering problem. Computer Engineering and Applications，2004(2)：44－46，84.)
[17] Chen J K，Lin Y J，Li J J，et al. A rough set method for the minimum vertex cover problem of graphs. Applied Soft Computing，2016，42：360－367.
[18] 王国胤，于 洪，杨大春. 基于条件信息熵的决策表约简. 计算机学报，2002，25(7)：759－766.(Wang G Y，Yu H，Yang D C. Decision table reduction based on conditional information entropy. Chinese Journal of Computers，2002，25(7)：759－766.)
PDF(780872 KB)
