The set covering problem (SCP) asks to choose a minimum cost family of
subsets from given $n$ subsets, which together covers the entire ground set.
In this paper, we propose a local search algorithm for SCP, which have the
following three features. (1) The use of 3-flip neighborhood, which is the
set of solutions obtainable from the current solution by exchanging at most
three subsets. As the size of 3-flip neighborhood is $O(n^3)$, the
neighborhood search becomes expensive if implemented naively. To overcome
this, we propose an efficient implementation that reduces the number of
candidates in the neighborhood without sacrificing the solution quality. (2)
We allow the search to visit infeasible region, and incorporate the
strategic oscillation technique. (3) The size reduction of the problem by
using the information from the Lagrangian relaxation is incorporated, which
turned out to be effective in solving very large instances. According to
computational comparisons on benchmark instances with other existing
heuristic algorithms for SCP, our algorithm performs quite effectively for
various types of problems, especially for very large-scale instances.