A 3-Flip Neighborhood Local Search for the Set Covering Problem
Mutsunori Yagiura, Masahiro Kishida and Toshihide Ibaraki
The set covering problem (SCP)
a minimum cost family of subsets
from n given subsets,
which together covers the entire ground set.
In this paper, we propose a local search algorithm for SCP,
which has the following three characteristics.
(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(n3),
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 the infeasible region,
and incorporate the strategic oscillation technique
realized by adaptive control of penalty weights.
(3) The size reduction of the problem by using the information
from the Lagrangian relaxation is incorporated,
which is indispensable for 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.
European Journal of Operational Research,
172 (2006) 472-499.
Back to the Paper List