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. 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.
    2. 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.
    3. 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.
    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. 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).
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Miguel A. Lejeune & Andrzej Ruszczyński, 2007. "An Efficient Trajectory Method for Probabilistic Production-Inventory-Distribution Problems," Operations Research, INFORMS, vol. 55(2), pages 378-394, April.
    10. O’Hanley, Jesse R. & Scaparra, M. Paola & García, Sergio, 2013. "Probability chains: A general linearization technique for modeling reliability in facility location and related problems," European Journal of Operational Research, Elsevier, vol. 230(1), pages 63-75.
    11. Sándor F. Tóth & Robert G. Haight & Luke W. Rogers, 2011. "Dynamic Reserve Selection: Optimal Land Retention with Land-Price Feedbacks," Operations Research, INFORMS, vol. 59(5), pages 1059-1078, October.
    12. Sanchirico, James N., 2003. "Designing a Cost-Effective Marine Reserve Network: A Bioeconomic Metapopulation Analysis," Discussion Papers 10624, Resources for the Future.
    13. Boyer, Tracy A., 2003. "The Wetland Restoration Site Selection Problem Under Wetland Mitigation Banking (WMB) in Minnesota," 2003 Annual meeting, July 27-30, Montreal, Canada 22189, American Agricultural Economics Association (New Name 2008: Agricultural and Applied Economics Association).
    14. Yongjia Song & James R. Luedtke & Simge Küçükyavuz, 2014. "Chance-Constrained Binary Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 735-747, November.
    15. Rahul Nair & Elise Miller-Hooks, 2011. "Fleet Management for Vehicle Sharing Operations," Transportation Science, INFORMS, vol. 45(4), pages 524-540, November.
    16. Qi Feng & Justin Jia & J. George Shanthikumar, 2019. "Dynamic Multisourcing with Dependent Supplies," Management Science, INFORMS, vol. 67(6), pages 2770-2786, June.
    17. Ruliffson, Jane A. & Haight, Robert G. & Homans, Frances R. & Gobster, Paul H., 2002. "Providing Equitable Spatial Distribution Of Protected Natural Areas In A Metropolitan Setting: An Application Of The Location Set-Covering Problem," 2002 Annual meeting, July 28-31, Long Beach, CA 19845, American Agricultural Economics Association (New Name 2008: Agricultural and Applied Economics Association).
    18. Laitila, Jussi & Moilanen, Atte, 2012. "Use of many low-level conservation targets reduces high-level conservation performance," Ecological Modelling, Elsevier, vol. 247(C), pages 40-47.
    19. Sankaranarayanan, Sriram & Feijoo, Felipe & Siddiqui, Sauleh, 2018. "Sensitivity and covariance in stochastic complementarity problems with an application to North American natural gas markets," European Journal of Operational Research, Elsevier, vol. 268(1), pages 25-36.
    20. Wang, Changjun & Chen, Shutong, 2020. "A distributionally robust optimization for blood supply network considering disasters," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 134(C).

    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.