Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2004-001 (March 9, 2004)

A 3-Flip Neighborhood Local Search for the Set Covering Problem
by Mutsunori Yagiura, Masahiro Kishida and Toshihide Ibaraki

PostScript File

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.