IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v53y2006i2p170-179.html
   My bibliography  Save this article

A new reformulation approach for the generalized partial covering problem

Author

Listed:
  • Youngho Lee
  • Hanif D. Sherali
  • Ikhyun Kwon
  • Seongin Kim

Abstract

In this paper, we consider a situation in which a group of facilities must be constructed in order to serve a given set of customers, where the facilities might not be able to guarantee an absolute coverage to the different customers. We examine the problem of maximizing the total service reliability of the system subject to a budgetary constraint. We propose a new reformulation of this problem that facilitates the generation of tight lower and upper bounds. These bounding mechanisms are embedded within the framework of a branch‐and‐bound procedure. Computational results on problem instances ranging in size up to 100 facilities and 200 customers reveal the efficacy of the proposed exact and heuristic approaches. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006

Suggested Citation

  • Youngho Lee & Hanif D. Sherali & Ikhyun Kwon & Seongin Kim, 2006. "A new reformulation approach for the generalized partial covering problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(2), pages 170-179, March.
    • Handle: RePEc:wly:navres:v:53:y:2006:i:2:p:170-179
    DOI: 10.1002/nav.20130
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.20130
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.20130?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
    ---><---

    References listed on IDEAS

    as
    1. Hanif D. Sherali & Seong‐In Kim & Edna L. Parrish, 1991. "Probabilistic partial set covering problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(1), pages 41-51, February.
    2. Marianov, Vladimir & Serra, Daniel, 2001. "Hierarchical location-allocation models for congested systems," European Journal of Operational Research, Elsevier, vol. 135(1), pages 195-208, November.
    3. Robert G. Haight & Charles S. Revelle & Stephanie A. Snyder, 2000. "An Integer Optimization Approach to a Probabilistic Reserve Site Selection Problem," Operations Research, INFORMS, vol. 48(5), pages 697-708, October.
    4. Egon Balas & Maria C. Carrera, 1996. "A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering," Operations Research, INFORMS, vol. 44(6), pages 875-890, December.
    5. Alberto Caprara & Matteo Fischetti & Paolo Toth, 1999. "A Heuristic Method for the Set Covering Problem," Operations Research, INFORMS, vol. 47(5), pages 730-743, October.
    6. Beasley, J. E. & Chu, P. C., 1996. "A genetic algorithm for the set covering problem," European Journal of Operational Research, Elsevier, vol. 94(2), pages 392-404, October.
    7. Alberto Caprara & Paolo Toth & Matteo Fischetti, 2000. "Algorithms for the Set Covering Problem," Annals of Operations Research, Springer, vol. 98(1), pages 353-371, December.
    8. Marshall L. Fisher & Pradeep Kedia, 1990. "Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics," Management Science, INFORMS, vol. 36(6), pages 674-688, June.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Hesham Rakha & Mazen Arafeh, 2010. "Calibrating Steady-State Traffic Stream and Car-Following Models Using Loop Detector Data," Transportation Science, INFORMS, vol. 44(2), pages 151-168, May.
    2. Timothy C. Y. Chan & Derya Demirtas & Roy H. Kwon, 2016. "Optimizing the Deployment of Public Access Defibrillators," Management Science, INFORMS, vol. 62(12), pages 3617-3635, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. 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.
    2. Gao, Chao & Yao, Xin & Weise, Thomas & Li, Jinlong, 2015. "An efficient local search heuristic with row weighting for the unicost set covering problem," European Journal of Operational Research, Elsevier, vol. 246(3), pages 750-761.
    3. Patrizia Beraldi & Andrzej Ruszczyński, 2002. "The Probabilistic Set-Covering Problem," Operations Research, INFORMS, vol. 50(6), pages 956-967, December.
    4. 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.
    5. 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.
    6. Lan, Guanghui & DePuy, Gail W. & Whitehouse, Gary E., 2007. "An effective and simple heuristic for the set covering problem," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1387-1403, February.
    7. Victor Reyes & Ignacio Araya, 2021. "A GRASP-based scheme for the set covering problem," Operational Research, Springer, vol. 21(4), pages 2391-2408, December.
    8. Bautista, Joaquín & Pereira, Jordi, 2006. "Modeling the problem of locating collection areas for urban waste management. An application to the metropolitan area of Barcelona," Omega, Elsevier, vol. 34(6), pages 617-629, December.
    9. Dimitris Bertsimas & Dan A. Iancu & Dmitriy Katz, 2013. "A New Local Search Algorithm for Binary Optimization," INFORMS Journal on Computing, INFORMS, vol. 25(2), pages 208-221, May.
    10. Naji-Azimi, Zahra & Toth, Paolo & Galli, Laura, 2010. "An electromagnetism metaheuristic for the unicost set covering problem," European Journal of Operational Research, Elsevier, vol. 205(2), pages 290-300, September.
    11. Kedong Yan & Dongjing Miao & Cui Guo & Chanying Huang, 2021. "Efficient feature selection for logical analysis of large-scale multi-class datasets," Journal of Combinatorial Optimization, Springer, vol. 42(1), pages 1-23, July.
    12. Ablanedo-Rosas, José H. & Rego, César, 2010. "Surrogate constraint normalization for the set covering problem," European Journal of Operational Research, Elsevier, vol. 205(3), pages 540-551, September.
    13. Alberto Caprara & Matteo Fischetti & Paolo Toth, 1999. "A Heuristic Method for the Set Covering Problem," Operations Research, INFORMS, vol. 47(5), pages 730-743, October.
    14. Li, Shengyin & Huang, Yongxi, 2014. "Heuristic approaches for the flow-based set covering problem with deviation paths," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 72(C), pages 144-158.
    15. Ran Wei & Alan Murray & Rajan Batta, 2014. "A bounding-based solution approach for the continuous arc covering problem," Journal of Geographical Systems, Springer, vol. 16(2), pages 161-182, April.
    16. Helena R. Lourenço & José P. Paixão & Rita Portugal, 2001. "Multiobjective Metaheuristics for the Bus Driver Scheduling Problem," Transportation Science, INFORMS, vol. 35(3), pages 331-343, August.
    17. Hernández-Leandro, Noberto A. & Boyer, Vincent & Salazar-Aguilar, M. Angélica & Rousseau, Louis-Martin, 2019. "A matheuristic based on Lagrangian relaxation for the multi-activity shift scheduling problem," European Journal of Operational Research, Elsevier, vol. 272(3), pages 859-867.
    18. Cochran, Jeffery K. & Marquez Uribe, Alberto, 2005. "A set covering formulation for agile capacity planning within supply chains," International Journal of Production Economics, Elsevier, vol. 95(2), pages 139-149, February.
    19. Owais, Mahmoud & Moussa, Ghada S. & Hussain, Khaled F., 2019. "Sensor location model for O/D estimation: Multi-criteria meta-heuristics approach," Operations Research Perspectives, Elsevier, vol. 6(C).
    20. Nguyen, Tri-Dung, 2014. "A fast approximation algorithm for solving the complete set packing problem," European Journal of Operational Research, Elsevier, vol. 237(1), pages 62-70.

    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:wly:navres:v:53:y:2006:i:2:p:170-179. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.