A rough set method for the unicost set covering problem
- PDF / 875,719 Bytes
- 12 Pages / 595.276 x 790.866 pts Page_size
- 48 Downloads / 275 Views
ORIGINAL ARTICLE
A rough set method for the unicost set covering problem Qingyuan Xu1 • Anhui Tan2 • Yaojin Lin1
Received: 27 July 2014 / Accepted: 15 April 2015 Springer-Verlag Berlin Heidelberg 2015
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. Keywords Unicost set covering problem Rough set Granular computing Local minimum Knowledge reduction
& Qingyuan Xu [email protected] & Anhui Tan [email protected] Yaojin Lin [email protected] 1
School of Computer Science, Minnan Normal University, Zhangzhou 363000, China
2
School of Mathematics and statistics, Minnan Normal University, Zhangzhou 363000, China
1 Introduction Rough set theory, proposed by Pawlak [24, 25], is a useful mathematical tool for uncertain, inexact and fuzzy knowledge. It has been widely used in data analysis, data mining, artificial intelligence [25, 27, 30, 37] and obtained extensive development [8, 21, 37–39, 44, 48, 50]. Knowledge reduction plays an important role in the theory of rough set. A reduct is a minimal subset of knowledge that remains the same classification ability as the whole knowledge [25, 26, 51]. Many approaches have been proposed for knowledge reduction [13, 22, 30, 32, 47, 51]. In which, the boolean logical operations based on discernibility matrix which were proposed by Skowron and Rauszer [30] is an accurate method to obtain all the reducts. It showed that the set of all reducts were in fact the set of prime implicants of the discernibility function. However, the time complexity of the boolean logical operations based on discernibility matrix is exponential with the size of the information system. Therefore, many heuristic algorithms were developed to find a single reduct, such as positive-region methods [7, 10, 29], information entropy methods [16, 28, 32, 46], discernibility matrix methods [5, 42, 43], and so on. The set covering problem (SCP) is a popular optimization problem that has been applied to a wide range of industrial applications, including scheduling, manufacturing, service planning, and location problems [1, 4, 12]. Various algorithms have been proposed to solve the SCP, such as exhaust algorithm, invisible enumeration [33], genetic algorithm [34] and others [35]. The time complexity of these algorithms exponentially increases with the size of the probl
Data Loading...
