Research On Methods Of Several Kinds Of Set Covering Problems

The set covering problem is a hot issue of combinatorial optimization problems.There are several crucial problems,such as the classical minimum set covering problem,the minimum weight set covering problem,the minimal set covering problem and the maximum set k-covering problem.All of them play an important role in both of theory and applications.This paper focuses on the above four problems in the set covering problem,which aims to design several efficient methods for solving these problems based on what their various needs.For some subproblems in the set covering problem,solving methods are mainly divided into two parts: exact methods and heuristic methods.When using exact methods to solve one problem,we can get the optimal solution.But as the size of this problem increases,exact methods fail to obtain a candidate solution,especially for massive problems.In addition,heuristic methods obtain a great candidate solution within a reasonable time,but cannot ensure that this candidate solution is a optimal solution.Therefore,heuristic methods are suitable for massive problems and some special problems that need not a high demand of a optimal solution.For solving the classical minimum set covering problem,the minimum weight set covering problem and the maximum set k-covering problem,since some massive instances of these problems need be solved and exact methods are hardly applied to solve these massive instances,three heuristic methods are proposed to solve these problems.However,for the minimal set covering problem,since the minimal set covering problem aims to obtain the optimal solution while heuristic methods cannot demonstrate that the candidate solution obtained is a solution optimal,an exact method is proposed to solve the minimal set covering problem.The main work of this paper are outlined as follows:1)Firstly,for the classical minimum set covering problem,this paper uses the formulation of hypergraph to represent this problem and then follows the general framework of the popular stochastic local search to design a new local search based method named u SLC,which is based on three novel strategies,i.e.a hyperedge selection strategy,a weight diversity strategy and a hyperedgeselection strategy.Specially,the strategy as called hyperedge configuration checking strategy aims to avoid the search trajectory which maybe leads to local optima.Additionally,a new weight diversity strategy is proposed for the diversification of search results though changing the weight of covered and uncovered vertices in the current candidate solution.Based on the above strategies,the hyperedge selection strategy is proposed to guide u SLC to obtain the better candidate solution.The experimental results show that our method u SLC significantly outperforms the state-of-the-art heuristic method EM by one to two orders of magnitudes on the 85 classical instances.Also,our method improves the current optimal solutions for 11 instances.2)Secondly,for solving the minimum weight set covering problem,this paper designs a new local search framework and then proposes a method called WSCLS,which is based on three new strategies,including a reduce preprocessing strategy,a low time complexity initialization strategy and a multivalued selection strategy.In details,a reduce preprocessing strategy is used to downscale this problem,further cutting down some unnecessary search space;a low-complexity initialization method is proposed to overcome the high complexity of the traditional initialization method;during removing subset process,a multivalued selection strategy is applied to decide which subset should be removed quickly and accurately.Experimental results show that the performance of WSCLS is much better than other competitors under most massive instances.3)Thirdly,the minimal set covering problem is also called the minimal hitting set problem.This paper uses a state-of-the-art CSP-solver to design a new method,called CSP-MHS.CSP-MHS converts the minimal hitting sets problem into the constraint satisfaction problems and then calls a state-of-the-art CSP-solver to obtain the optimal solution.Moreover,the concepts of hard-conflict sets and soft-conflict sets are proposed.Then this paper applies CSP-MHS to solve the minimal hitting sets which have some features including less than a fixed length,not including some specific elements,and including hard-conflict sets and soft-conflict sets.Compared with a state-of-the-art exact method,CSP-MHS can use less time to obtain the optimal solution.4)Finally,in order to solve the maximum set k-covering problem,this paper proposes a restart local search method,which is called RNKC.RNKCimproves the procedure of random restart mechanism and neighborhood search method.During the initialization procedure,RNKC uses a new random restart method to greatly deal with the serious cycling problem in local search methods.During the construction procedure,owing to the novel neighborhood search method,RNKC allows a neighborhood exploration to reach as much as possible.Moreover,it makes us obtain some better solution quality.Comprehensive results on the classical instances show that the RNKC method competes very favorably with the famous commercial solver CPLEX.In particular,though our method,the better optimal solution can be found in a shorter time for some instances.