Algorithm Research Based On Scoring Mechanism And Configuration Checking For The Set K-covering Problem

The set covering problem is not only a classic combinational optimization problem in operational research,but also a common problem in computer science.The set k-covering problem,which is the extension problem of the set covering problem,adds some constraints and raises the difficulty level of the problem.The set k-covering problem(SKCP)is NP-hard and has important real-world applications,such as network security,resource allocation,personnel assignment and so on.In this paper,we propose several improvements over typical algorithms for its solution.First,we present a multilevel(ML)score heuristic that reflects relevant information of the currently selected subsets inside or outside a candidate solution.Next,we propose quantitative configuration checking(QCC)to overcome the cycling problem in local search.Based on the ML heuristic and QCC strategy,we propose an effective subset selection strategy.Then,we integrate these methods into a local search algorithm,which we called MLQCC.In addition,we propose a preprocessing method to reduce the scale of the original problem before applying MLQCC.We further enhance MLQCC for large-scale instances by using a low-time-complexity initialization algorithm to determine an initial candidate solution,obtaining the MLQCC+LI algorithm.We choose some recognized and representative experimental examples.The performance of the proposed MLQCC and MLQCC+LI is verified through experimental evaluations on both classical and large-scale benchmarks.The results show that MLQCC and MLQCC+LI notably outperform several state-of-the-art SKCP algorithms on the evaluated benchmarks.