A LOCAL-SEARCH HEURISTIC FOR LARGE SET-COVERING PROBLEMS

In this note we describe a local-search heuristic (LSH) for large non- unicost set-covering problems (SCPs). The new heuristic is based on th e simulated annealing algorithm and uses an improvement routine design ed to provide low-cost solutions within a reasonable amount of CPU tim e. The solution costs associated with the LSH compared very favorably to the best previously published solution costs for 20 large SCPs take n from the literature. In particular, the LSH yielded new benchmark so lutions for 17 of the 20 test problems. We also report that, for SCPs where column cost is correlated with column coverage, the new heuristi c provides solution costs competitive with previously published result s for comparable problems. (C) 1995 John Wiley & Sons, Inc.