An improved configuration checking-based algorithm for the unicost set covering problem

摘要

Configuration Checking (CC) is a simple tool that can be added to local search algorithms to prevent cycling. The generic forms of CC and local search may not be suitable to solve large-scale unicost set covering problem (USCP) instances. Thus, in this study, we introduce an improved CC-based algorithm to solve USCPs. Unlike previous CC implementations that only consider subset states to prevent cycling, the proposed algorithm also checks the element states to minimize the number of subsets, in order to cut down unnecessary search spaces. Therefore, we refer to this technique as the element-state configuration checking (ES-CC) algorithm. Moreover, in our proposed algorithm, the score value (a numerical measure to differentiate between subsets) considers multiple levels of element covering. This multi-level scoring (MLS) value is a new powerful contribution compared to the single-level scoring used in previous CC algorithms. Using these two novel ideas, MLS and ES-CC, we implement the new MLSES-CC algorithm to solve the USCP. The MLSES-CC algorithm also implements a more aggressive local search routine that simultaneously changes the status of the three subsets. We use the MLSES-CC algorithm to solve 176 USCP instances that belong to standard and novel benchmarking sets and compare our results to the bestknown USCP algorithms, in terms of solution quality and computation time. Computational experiments indicate that the MLSES-CC algorithm can be considered as a new state-of-the-art algorithm to solve USCPs.