Article ID: | iaor2000551 |
Country: | Netherlands |
Volume: | 86 |
Issue: | 1 |
Start Page Number: | 611 |
End Page Number: | 627 |
Publication Date: | Mar 1999 |
Journal: | Annals of Operations Research |
Authors: | Jacobs Larry W., Thompson Gary M., Brusco Michael J. |
Keywords: | optimization: simulated annealing |
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.