A Morphing Procedure to Supplement a Simulated Annealing Heuristic for Cost- and Coverage-Correlated Set-Covering Problems
dc.contributor.author | Brusco, Michael J. | |
dc.contributor.author | Jacobs, Larry W. | |
dc.contributor.author | Thompson, Gary | |
dc.date.accessioned | 2020-09-12T21:14:04Z | |
dc.date.available | 2020-09-12T21:14:04Z | |
dc.date.issued | 1999-01-01 | |
dc.description.abstract | We report on the use of a morphing procedure in a simulated annealing (SA) heuristic developed for set-covering problems (SCPs). Morphing enables the replacement of columns in solution with similar but more effective columns (morphs). We developed this procedure to solve minimum cardinality set-covering problems (MCSCPs) containing columns which exhibit high degrees of coverage correlation, and weighted set-covering problems (WSCPs) that exhibit high degrees of both cost correlation and coverage correlation. Such correlation structures are contained in a wide variety of real-world problems including many scheduling, design, and location applications. In a large computational study, we found that the morphing procedure does not degrade the performance of an SA heuristic for SCPs with low degrees of cost and coverage correlation (given a reasonable amount of computation time), and that it improves the performance of an SA heuristic for problems with high degrees of such correlations. | |
dc.description.legacydownloads | Thompson30.pdf: 54 downloads, before Aug. 1, 2020. | |
dc.identifier.other | 12735670 | |
dc.identifier.uri | https://hdl.handle.net/1813/72450 | |
dc.language.iso | en_US | |
dc.relation.doi | https://doi.org/10.1023/A:1018900128545 | |
dc.rights | Required Publisher Statement: © Springer. Reprinted with permission. All rights reserved. Final version published as: Brusco, M. J., Jacobs, L. W., & Thompson, G. M. (1999). A morphing procedure to supplement a simulated annealing heuristic for cost‐ and coverage‐correlated set‐covering problems. Annals of Operations Research, 86(0), 611-627. doi: 10.1023/A:1018900128545 | |
dc.subject | set covering | |
dc.subject | heuristics | |
dc.title | A Morphing Procedure to Supplement a Simulated Annealing Heuristic for Cost- and Coverage-Correlated Set-Covering Problems | |
dc.type | article | |
local.authorAffiliation | Brusco, Michael J.: Florida State University | |
local.authorAffiliation | Jacobs, Larry W.: Northern Illinois University | |
local.authorAffiliation | Thompson, Gary: gmt1@cornell.edu Cornell University School of Hotel Administration |
Files
Original bundle
1 - 1 of 1