A Combined Data Mining Based-Bi Clustering and Order Preserved Sub-Matrices Algorithm for Set Covering Problem

Document Type : Research Paper


1 Semnan University

2 Department of industrial engineering, Semnan university, semnan, Iran

3 Department of Industrial Engineering, Semnan University, Semnan, Iran.



In this paper, we discuss the set covering problem (SCP), an extension of the original demand covering problem and present several potential applications. The objective of the well-known demand covering problem is to select appropriate locations for a number of facilities (servers) such that a given demand set is sufficiently covered. The SCP tries to minimize location cost satisfying a specified level of coverage. The SCP can be applied to various location problems, e.g. the provision of emergency services where alternative facilities need to hedge against the unavailability of the primary facility, as well as to other domains, e.g. recommender systems where it may be desirable to respond to each user query with more than one available choice that satisfy their preferences. We efficiently solve the SCP by using a biclustering method, which creates biclusters from the distance matrix. In the proposed approach, a bicluster represents a subset of demand points covered by a subset of facilities. The heuristic selects appropriate biclusters taking into account the objective of the problem. Based on experimental tests performed in known benchmark problems, we observed that our method provides solutions slightly inferior to the optimal ones in significantly less computational time when compared to the GAMS optimizer. In larger test instances, our method outperforms GAMS both in terms of computational time and solution quality, when a time bound of 1 h is set for obtaining a solution.