  In this paper we present a heuristic for the non-unicost set covering problem
using local branching. Local branching eliminates the need to define a problem
specific search neighbourhood for any particular (zero-one) optimisation
problem. It does this by incorporating a generalised Hamming distance
neighbourhood into the problem, and this leads naturally to an appropriate
neighbourhood search procedure. We apply our approach to the non-unicost set
covering problem. Computational results are presented for 65 test problems that
have been widely considered in the literature. Our results indicate that our
heuristic is better than six of the eight other heuristics we examined,
slightly worse than that of one heuristic, but that there is a single heuristic
that out-performs all others. We believe that the work described here
illustrates that the potential for using local branching, operating as a
stand-alone matheuristic, has not been fully exploited in the literature.
