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

• DOI: 10.1111/itor.12614
• Publication Date: 2018-11-16T17:39:11Z
• Authors: Yiyuan Wang; Chenxi Li; Huanyao Sun; Jiejiang Chen; Minghao Yin
• Keywords: Initialization

Abstract The 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, present a multilevel (ML) score heuristic that reflects relevant information of the currently selected subsets inside or outside candidate Next, QCC to overcome cycling in local search. Based on ML strategy, an effective subset selection strategy. Then, integrate these methods into search algorithm, which called MLQCC. addition, preprocessing method reduce scale original before applying We further enhance MLQCC large‐scale instances using low‐time‐complexity initialization algorithm determine initial solution, obtaining + LI algorithm. performance proposed verified through experimental evaluations both classical benchmarks. results show notably outperform state‐of‐the‐art SKCP evaluated