A novel local search algorithm with configuration checking and scoring mechanism for the set k‐covering problem. (20th April 2016)

• Record Type: Journal Article
• Authors: Wang, Yiyuan; Yin, Minghao; Ouyang, Dantong; Zhang, Liming
• Is Part Of: International transactions in operational research. Volume 24:Number 6(2017)
• Page Start: 1463
• Page End: 1485
• Publication Date: 2016-04-20
• Subjects: set k‐covering problem -- configuration checking -- scoring mechanism -- local search; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12280
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: The set k ‐covering problem, an extension of the classical set covering problem, is an important NP‐hard combinatorial optimization problem with extensive applications, including computational biology and wireless network. The aim of this paper is to design a new local search algorithm to solve this problem. First, to overcome the cycling problem in local search, the set k ‐covering configuration checking (SKCC) strategy is proposed. Second, we use the cost scheme of elements to define the scoring mechanism so that our algorithm can find different possible good‐quality solutions. Having combined the SKCC strategy with the scoring mechanism, a subset selection strategy is designed to decide which subset should be selected as a candidate solution component. After that, a novel local search framework, as we call DLLccsm (diversion local search based on configuration checking and scoring mechanism), is proposed. DLLccsm is evaluated against two state‐of‐the‐art algorithms. The experimental results show that DLLccsm performs better than its competitors in terms of solution quality in most classical instances.