An implementation of harmony search algorithm to the set covering problem

The set covering problem (SCP) seeks to find a subset of columns that have the least sum of costs to cover a set of rows. It is an NP-hard problem, and finds a lot of real world applications. In this paper, we present a harmony search algorithm (HSA) to solve the SCP. It uses a greedy construction procedure to generate an initial harmony memory, and presents a repair operator to guarantee the feasibility of new generated solutions. New solutions are further improved by a local search procedure. The HSA is tested on 45 instances from literature. Simulation results and comparisons show that HSA can get high quality solutions of the set covering problem.