IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v61y2013i2p438-452.html
   My bibliography  Save this article

Probabilistic Set Covering with Correlations

Author

Listed:
  • Shabbir Ahmed

    (School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Dimitri J. Papageorgiou

    (School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

Abstract

We consider two variants of a probabilistic set covering (PSC) problem. The first variant assumes that there is uncertainty regarding whether a selected set can cover an item, and the objective is to determine a minimum-cost combination of sets so that each item is covered with a prespecified probability. The second variant seeks to maximize the minimum probability that a selected set can cover all items. To date, literature on this problem has focused on the special case in which uncertainties are independent. In this paper, we formulate deterministic mixed-integer programming models for distributionally robust PSC problems with correlated uncertainties. By exploiting the supermodularity of certain substructures and analyzing their polyhedral properties, we develop strong valid inequalities to strengthen the formulations. Computational results illustrate that our modeling approach can outperform formulations in which correlations are ignored and that our algorithms can significantly reduce overall computation time.

Suggested Citation

  • Shabbir Ahmed & Dimitri J. Papageorgiou, 2013. "Probabilistic Set Covering with Correlations," Operations Research, INFORMS, vol. 61(2), pages 438-452, April.
    • Handle: RePEc:inm:oropre:v:61:y:2013:i:2:p:438-452
    DOI: 10.1287/opre.1120.1135
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1120.1135
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1120.1135?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. Shipra Agrawal & Yichuan Ding & Amin Saberi & Yinyu Ye, 2012. "Price of Correlations in Stochastic Optimization," Operations Research, INFORMS, vol. 60(1), pages 150-162, February.
    2. Patrizia Beraldi & Andrzej Ruszczyński, 2002. "The Probabilistic Set-Covering Problem," Operations Research, INFORMS, vol. 50(6), pages 956-967, December.
    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. Patrizia Beraldi & Maria Bruni, 2010. "An exact approach for solving integer problems under probabilistic constraints with random technology matrix," Annals of Operations Research, Springer, vol. 177(1), pages 127-137, 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. Alper Atamtürk & Andrés Gómez, 2017. "Maximizing a Class of Utility Functions Over the Vertices of a Polytope," Operations Research, INFORMS, vol. 65(2), pages 433-445, March-Apr.
    2. Mahdi Noorizadegan & Abbas Seifi, 2018. "An efficient computational method for large scale surgery scheduling problems with chance constraints," Computational Optimization and Applications, Springer, vol. 69(2), pages 535-561, March.
    3. Yang, Jun & Alajaji, Fady & Takahara, Glen, 2016. "On bounding the union probability using partial weighted information," Statistics & Probability Letters, Elsevier, vol. 116(C), pages 38-44.
    4. Gianpiero Canessa & Julian A. Gallego & Lewis Ntaimo & Bernardo K. Pagnoncelli, 2019. "An algorithm for binary linear chance-constrained problems using IIS," Computational Optimization and Applications, Springer, vol. 72(3), pages 589-608, April.
    5. Zhouchun Huang & Qipeng P. Zheng & Eduardo L. Pasiliao & Daniel Simmons, 2017. "Exact algorithms on reliable routing problems under uncertain topology using aggregation techniques for exponentially many scenarios," Annals of Operations Research, Springer, vol. 249(1), pages 141-162, February.
    6. Liu, Kanglin & Zhang, Hengliang & Zhang, Zhi-Hai, 2021. "The efficiency, equity and effectiveness of location strategies in humanitarian logistics: A robust chance-constrained approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).

    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. Zhouchun Huang & Qipeng P. Zheng & Eduardo L. Pasiliao & Daniel Simmons, 2017. "Exact algorithms on reliable routing problems under uncertain topology using aggregation techniques for exponentially many scenarios," Annals of Operations Research, Springer, vol. 249(1), pages 141-162, February.
    2. Billionnet, Alain, 2011. "Solving the probabilistic reserve selection problem," Ecological Modelling, Elsevier, vol. 222(3), pages 546-554.
    3. Ruliffson, Jane A. & Haight, Robert G. & Gobster, Paul H. & Homans, Frances R., 2001. "Exploring Goal Tradeoffs In Metropolitan Natural Area Protection," 2001 Annual meeting, August 5-8, Chicago, IL 20642, American Agricultural Economics Association (New Name 2008: Agricultural and Applied Economics Association).
    4. Jeffrey D. Camm & Susan K. Norman & Stephen Polasky & Andrew R. Solow, 2002. "Nature Reserve Site Selection to Maximize Expected Species Covered," Operations Research, INFORMS, vol. 50(6), pages 946-955, December.
    5. Miguel A. Lejeune & François Margot, 2016. "Solving Chance-Constrained Optimization Problems with Stochastic Quadratic Inequalities," Operations Research, INFORMS, vol. 64(4), pages 939-957, August.
    6. Stephanie A. Snyder & Robert G. Haight, 2016. "Application of the Maximal Covering Location Problem to Habitat Reserve Site Selection," International Regional Science Review, , vol. 39(1), pages 28-47, January.
    7. Benoumechiara Nazih & Bousquet Nicolas & Michel Bertrand & Saint-Pierre Philippe, 2020. "Detecting and modeling critical dependence structures between random inputs of computer models," Dependence Modeling, De Gruyter, vol. 8(1), pages 263-297, January.
    8. Benoumechiara Nazih & Bousquet Nicolas & Michel Bertrand & Saint-Pierre Philippe, 2020. "Detecting and modeling critical dependence structures between random inputs of computer models," Dependence Modeling, De Gruyter, vol. 8(1), pages 263-297, January.
    9. Marshalek, Elaina C. & Ramage, Benjamin S. & Potts, Matthew D., 2014. "Integrating harvest scheduling and reserve design to improve biodiversity conservation," Ecological Modelling, Elsevier, vol. 287(C), pages 27-35.
    10. Hayri Önal & Robert A. Briers, 2006. "Optimal Selection of a Connected Reserve Network," Operations Research, INFORMS, vol. 54(2), pages 379-388, April.
    11. Steffen Rebennack, 2022. "Data-driven stochastic optimization for distributional ambiguity with integrated confidence region," Journal of Global Optimization, Springer, vol. 84(2), pages 255-293, October.
    12. Yıldız, Barış & Olcaytu, Evren & Şen, Ahmet, 2019. "The urban recharging infrastructure design problem with stochastic demands and capacitated charging stations," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 22-44.
    13. Sundararajan, Mukund & Yan, Qiqi, 2020. "Robust mechanisms for risk-averse sellers," Games and Economic Behavior, Elsevier, vol. 124(C), pages 644-658.
    14. Weerasena, Lakmali & Shier, Douglas & Tonkyn, David & McFeaters, Mark & Collins, Christopher, 2023. "A sequential approach to reserve design with compactness and contiguity considerations," Ecological Modelling, Elsevier, vol. 478(C).
    15. Hu, Xiaoxuan & Zhu, Waiming & Ma, Huawei & An, Bo & Zhi, Yanling & Wu, Yi, 2021. "Orientational variable-length strip covering problem: A branch-and-price-based algorithm," European Journal of Operational Research, Elsevier, vol. 289(1), pages 254-269.
    16. Büsing, Christina & Comis, Martin & Schmidt, Eva & Streicher, Manuel, 2021. "Robust strategic planning for mobile medical units with steerable and unsteerable demands," European Journal of Operational Research, Elsevier, vol. 295(1), pages 34-50.
    17. Mengshi Lu & Lun Ran & Zuo-Jun Max Shen, 2015. "Reliable Facility Location Design Under Uncertain Correlated Disruptions," Manufacturing & Service Operations Management, INFORMS, vol. 17(4), pages 445-455, October.
    18. M A Lejeune, 2008. "Preprocessing techniques and column generation algorithms for stochastically efficient demand," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(9), pages 1239-1252, September.
    19. Lukáš Adam & Martin Branda, 2016. "Nonlinear Chance Constrained Problems: Optimality Conditions, Regularization and Solvers," Journal of Optimization Theory and Applications, Springer, vol. 170(2), pages 419-436, August.
    20. Tajibaeva, Liaila & Haight, Robert & Stephen, Polasky, 2014. "Welfare and Biodiversity Tradeoffs in Urban Open Space Protection," 2014 Annual Meeting, July 27-29, 2014, Minneapolis, Minnesota 170602, Agricultural and Applied Economics Association.

    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:inm:oropre:v:61:y:2013:i:2:p:438-452. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.