A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated set-covering problems

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-cove...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 1999-01, Vol.86, p.611
Main Authors: Brusco, Michael J, Jacobs, Larry W, Thompson, Gary M
Format: Article
Language:English
Subjects:
Algorithms
Heuristic
Metallurgy
Operations research
Part time employment
Studies
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. [PUBLICATION ABSTRACT]
ISSN:0254-5330
1572-9338
DOI:10.1023/a:1018900128545