Loading...
Please wait, while we are loading the content...
Similar Documents
A 3-flip neighborhood local search for the set covering problem (2003).
| Content Provider | CiteSeerX |
|---|---|
| Author | Yagiura, Mutsunori Kishida, Masahiro Ibaraki, Toshihide |
| Abstract | The set covering problem (SCP) calls for 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 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³), 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. |
| File Format | |
| Publisher Date | 2003-01-01 |
| Access Restriction | Open |
| Subject Keyword | Entire Ground Set Solution Quality Set Covering Problem Lagrangian Relaxation Efficient Implementation Current Solution Minimum Cost Family 3-flip Neighborhood Local Search Large Instance 3-flip Neighborhood Various Type Strategic Oscillation Technique Large-scale Instance Computational Comparison Neighborhood Search Size Reduction Local Search Algorithm Heuristic Algorithm Benchmark Instance Infeasible Region |
| Content Type | Text |
