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.