A LOCAL-SEARCH HEURISTIC FOR LARGE SET-COVERING PROBLEMS

Citation
Lw. Jacobs et Mj. Brusco, A LOCAL-SEARCH HEURISTIC FOR LARGE SET-COVERING PROBLEMS, Naval research logistics, 42(7), 1995, pp. 1129-1140
Citations number
36
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science","Engineering, Marine
Journal title
ISSN journal
0894069X
Volume
42
Issue
7
Year of publication
1995
Pages
1129 - 1140
Database
ISI
SICI code
0894-069X(1995)42:7<1129:ALHFLS>2.0.ZU;2-8
Abstract
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.