IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v86y1999i0p611-62710.1023-a1018900128545.html
   My bibliography  Save this article

A morphing procedure to supplement a simulated annealing heuristic for cost‐ andcoverage‐correlated set‐covering problems

Author

Listed:
  • M.J. Brusco
  • L.W. Jacobs
  • G.M. Thompson

Abstract

We report on the use of a morphing procedure in a simulated annealing (SA) heuristicdeveloped for set‐covering problems (SCPs). Morphing enables the replacement of columnsin solution with similar but more effective columns (morphs). We developed this procedureto solve minimum cardinality set‐covering problems (MCSCPs) containing columns whichexhibit high degrees of coverage correlation, and weighted set‐covering problems (WSCPs)that exhibit high degrees of both cost correlation and coverage correlation. Such correlationstructures 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 morphingprocedure does not degrade the performance of an SA heuristic for SCPs with low degreesof cost and coverage correlation (given a reasonable amount of computation time), and thatit improves the performance of an SA heuristic for problems with high degrees of suchcorrelations. Copyright Kluwer Academic Publishers 1999

Suggested Citation

  • M.J. Brusco & L.W. Jacobs & G.M. Thompson, 1999. "A morphing procedure to supplement a simulated annealing heuristic for cost‐ andcoverage‐correlated set‐covering problems," Annals of Operations Research, Springer, vol. 86(0), pages 611-627, January.
    • Handle: RePEc:spr:annopr:v:86:y:1999:i:0:p:611-627:10.1023/a:1018900128545
    DOI: 10.1023/A:1018900128545
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1023/A:1018900128545
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1023/A:1018900128545?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Goodson, Justin C. & Ohlmann, Jeffrey W. & Thomas, Barrett W., 2012. "Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand," European Journal of Operational Research, Elsevier, vol. 217(2), pages 312-323.
    2. Jordi Pereira & Igor Averbakh, 2013. "The Robust Set Covering Problem with interval data," Annals of Operations Research, Springer, vol. 207(1), pages 217-235, August.
    3. Thompson, Gary M. & Goodale, John C., 2006. "Variable employee productivity in workforce scheduling," European Journal of Operational Research, Elsevier, vol. 170(2), pages 376-390, April.
    4. Victor Reyes & Ignacio Araya, 2021. "A GRASP-based scheme for the set covering problem," Operational Research, Springer, vol. 21(4), pages 2391-2408, December.
    5. Brusco, Michael J., 2014. "A comparison of simulated annealing algorithms for variable selection in principal component analysis and discriminant analysis," Computational Statistics & Data Analysis, Elsevier, vol. 77(C), pages 38-53.
    6. Vié, Marie-Sklaerder & Zufferey, Nicolas & Cordeau, Jean-François, 2019. "Solving the Wire-Harness Design Problem at a European car manufacturer," European Journal of Operational Research, Elsevier, vol. 272(2), pages 712-724.
    7. Yagiura, Mutsunori & Kishida, Masahiro & Ibaraki, Toshihide, 2006. "A 3-flip neighborhood local search for the set covering problem," European Journal of Operational Research, Elsevier, vol. 172(2), pages 472-499, July.
    8. Wang, Yiyuan & Pan, Shiwei & Al-Shihabi, Sameh & Zhou, Junping & Yang, Nan & Yin, Minghao, 2021. "An improved configuration checking-based algorithm for the unicost set covering problem," European Journal of Operational Research, Elsevier, vol. 294(2), pages 476-491.
    9. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar, 2015. "A set covering approach for multi-depot train driver scheduling," Journal of Combinatorial Optimization, Springer, vol. 29(3), pages 636-654, April.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:86:y:1999:i:0:p:611-627:10.1023/a:1018900128545. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.