A weighting-based local search heuristic algorithm for the Set Covering Problem

Abstract

The Set Covering Problem (SCP) is NP-hard and has many applications. In this paper, we introduce a heuristic algorithm for SCPs based on weighting. In our algorithm, a local search framework is proposed to perturb the candidate solution under the best objective value found during the search, a weighting scheme and several search strategies are adopted to help escape from local optima and make the search more divergent. The effectiveness of our algorithm is evaluated on a set of instances from the OR-Library and Steiner triple systems. The experimental results show that it is very competitive, for it is able to find all the optima or best known results with very small runtimes on non-unicost instances from the OR-Library and outperforms two excellent solvers we have found in literature on the unicost instances from Steiner triple systems. Furthermore, it is conceptually simple and only needs one parameter to indicate the stopping criterion.