Fixed Set Search Applied to the Maximum Set K-Covering Problem

The MKCP (Maximum Set k-Covering Problem) is a widely recognized combinatorial problem that falls under the category of NP-hard problems. It has diverse applications and involves the goal of covering a maximum number of elements using a limited number of candidate sets. In this paper, the novel fixed set search (FSS), a population based metaheuristic, is applied on the problem of interest. The FSS adds a learning mechanism to the greedy randomized adaptive search procedure (GRASP) based on elements frequently occurring in high quality solutions. The main advantage of the proposed approach is the simplicity of implementation compared to the current state-of-the-art methods. The conducted computational experiments show that the FSS even when using a simple local search manages to be highly competitive to state-of-the-art methods. In addition, the FSS manages to find two new lower bounds for the standardly used benchmark test instances. Finally, the performed computational experiments show that the learning mechanism of the FSS significantly improves the performance of the underlying GRASP algorithm.