Premium
Note: A local‐search heuristic for large set‐covering problems
Author(s) -
Jacobs Larry W.,
Brusco Michael J.
Publication year - 1995
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199510)42:7<1129::aid-nav3220420711>3.0.co;2-m
Subject(s) - heuristic , benchmark (surveying) , simulated annealing , set (abstract data type) , mathematical optimization , computer science , set cover problem , column (typography) , local search (optimization) , operations research , mathematics , programming language , telecommunications , geodesy , frame (networking) , geography
In this note we describe a local‐search heuristic (LSH) for large non‐unicost set‐covering problems (SCPs). The new heuristic is based on the simulated annealing algorithm and uses an improvement routine designed to provide low‐cost solutions within a reasonable amount of CPU time. The solution costs associated with the LSH compared very favorably to the best previously published solution costs for 20 large SCPs taken from the literature. In particular, the LSH yielded new benchmark solutions for 17 of the 20 test problems. We also report that, for SCPs where column cost is correlated with column coverage, the new heuristic provides solution costs competitive with previously published results for comparable problems. © 1995 John Wiley & Sons, Inc.