MLQCC: an improved local search algorithm for the set k‐covering problem

0202 electrical engineering, electronic engineering, information engineering 02 engineering and technology
DOI: 10.1111/itor.12614 Publication Date: 2018-11-16T17:39:11Z
ABSTRACT
AbstractThe set k‐covering problem (SKCP) is NP‐hard and has important real‐world applications. 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 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 using a low‐time‐complexity initialization algorithm to determine an initial candidate solution, obtaining the MLQCC + LI algorithm. 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.
SUPPLEMENTAL MATERIAL
Coming soon ....
REFERENCES (44)
CITATIONS (6)
EXTERNAL LINKS
PlumX Metrics
RECOMMENDATIONS
FAIR ASSESSMENT
Coming soon ....
JUPYTER LAB
Coming soon ....