IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v91y2025i4d10.1007_s10898-025-01472-x.html
   My bibliography  Save this article

Stochastic red-blue set covering: a decomposition approach

Author

Listed:
  • David Islip

    (University of Toronto)

  • Roy H. Kwon

    (University of Toronto)

Abstract

This work presents the two-stage stochastic red-blue set covering problem (2S-SRBSC). The red-blue set covering problem (RBSC) selects a subcollection of sets to cover all the blue elements while minimizing the number of red elements covered. Although RBSC has many application areas, such as classification and fraud detection, it does not capture randomness related to set membership and color uncertainty or any sense of recourse in response to the uncertainty. This work motivates these considerations via a fraud-prevention problem mortgage lenders face in practice. 2S-SRBSC is introduced to address this. In the proposed problem, uncertainty is represented via scenarios, and the decision-maker pays for sets in the first stage and has recourse to cover blue elements in the second stage that remain uncovered post-uncertainty. Different variants of 2S-SRBSC are considered, highlighting how they can model the real-life problem mortgage lenders face. In the case of 2S-SRBSC with simple recourse, a Benders decomposition (BD) and Benders dual decomposition (BDD) are presented and implemented in a commercial branch-and-cut solver. The resulting BDD subproblems yield cuts that are significantly tighter than those BD produces. The decompositions are tested and offer improvements in terms of solution quality and time for large-scale instances relative to the extensive form. Furthermore, the BDD exhibits desirable performance for instances where the commercial solver can quickly solve the mixed-binary subproblems. This work presents the first computational experience with decomposition algorithms applied to 2S-SRBSC problems.

Suggested Citation

  • David Islip & Roy H. Kwon, 2025. "Stochastic red-blue set covering: a decomposition approach," Journal of Global Optimization, Springer, vol. 91(4), pages 923-951, April.
  • Handle: RePEc:spr:jglopt:v:91:y:2025:i:4:d:10.1007_s10898-025-01472-x
    DOI: 10.1007/s10898-025-01472-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-025-01472-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10898-025-01472-x?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.

    References listed on IDEAS

    as
    1. Kiana Basiri & Babak Mahmoudi, 2021. "Possible income misstatement on mortgage loan applications: Evidence from the Canadian housing market," Real Estate Economics, American Real Estate and Urban Economics Association, vol. 49(3), pages 917-935, September.
    2. Hao-Hsiang Wu & Simge Küçükyavuz, 2018. "A two-stage stochastic programming approach for influence maximization in social networks," Computational Optimization and Applications, Springer, vol. 69(3), pages 563-595, April.
    3. Cordeau, Jean-François & Furini, Fabio & Ljubić, Ivana, 2019. "Benders decomposition for very large scale partial set covering and maximal covering location problems," European Journal of Operational Research, Elsevier, vol. 275(3), pages 882-896.
    4. Markus Leitner & Ivana Ljubić & Martin Luipersbeck & Markus Sinnl, 2018. "Decomposition methods for the two-stage stochastic Steiner tree problem," Computational Optimization and Applications, Springer, vol. 69(3), pages 713-752, April.
    5. Kiho Seo & Seulgi Joung & Chungmok Lee & Sungsoo Park, 2022. "A Closest Benders Cut Selection Scheme for Accelerating the Benders Decomposition Algorithm," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2804-2827, September.
    6. Arjan Reurink, 2018. "Financial Fraud: A Literature Review," Journal of Economic Surveys, Wiley Blackwell, vol. 32(5), pages 1292-1325, December.
    7. Ragheb Rahmaniani & Shabbir Ahmed & Teodor Gabriel Crainic & Michel Gendreau & Walter Rei, 2020. "The Benders Dual Decomposition Method," Operations Research, INFORMS, vol. 68(3), pages 878-895, May.
    8. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    9. Santoso, Tjendera & Ahmed, Shabbir & Goetschalckx, Marc & Shapiro, Alexander, 2005. "A stochastic programming approach for supply chain network design under uncertainty," European Journal of Operational Research, Elsevier, vol. 167(1), pages 96-115, November.
    10. George B. Dantzig, 1955. "Linear Programming under Uncertainty," Management Science, INFORMS, vol. 1(3-4), pages 197-206, 04-07.
    Full references (including those not matched with items on IDEAS)

    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. Güney, Evren & Leitner, Markus & Ruthmair, Mario & Sinnl, Markus, 2021. "Large-scale influence maximization via maximal covering location," European Journal of Operational Research, Elsevier, vol. 289(1), pages 144-164.
    2. Fei, Xin & Gülpınar, Nalân & Branke, Jürgen, 2019. "Efficient solution selection for two-stage stochastic programs," European Journal of Operational Research, Elsevier, vol. 277(3), pages 918-929.
    3. Maher, Stephen J., 2021. "Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework," European Journal of Operational Research, Elsevier, vol. 290(2), pages 479-498.
    4. Qian Zhang & Shuaian Wang & Lu Zhen, 2024. "Yard truck retrofitting and deployment for hazardous material transportation in green ports," Annals of Operations Research, Springer, vol. 343(3), pages 981-1012, December.
    5. Daniel Baena & Jordi Castro & Antonio Frangioni, 2020. "Stabilized Benders Methods for Large-Scale Combinatorial Optimization, with Application to Data Privacy," Management Science, INFORMS, vol. 66(7), pages 3051-3068, July.
    6. Lin, Yun Hui & Wang, Yuan & Lee, Loo Hay & Chew, Ek Peng, 2022. "Omnichannel facility location and fulfillment optimization," Transportation Research Part B: Methodological, Elsevier, vol. 163(C), pages 187-209.
    7. Rodríguez, Jesús A. & Anjos, Miguel F. & Côté, Pascal & Desaulniers, Guy, 2021. "Accelerating Benders decomposition for short-term hydropower maintenance scheduling," European Journal of Operational Research, Elsevier, vol. 289(1), pages 240-253.
    8. Ashkan Fakhri & Antonios Fragkogios & Georgios K. D. Saharidis, 2021. "An Accelerated Benders Decomposition Algorithm for Solving a Double-Type Double-Standard Maximal Covering Location Problem," SN Operations Research Forum, Springer, vol. 2(1), pages 1-24, March.
    9. Ljubić, Ivana & Pozo, Miguel A. & Puerto, Justo & Torrejón, Alberto, 2024. "Benders decomposition for the discrete ordered median problem," European Journal of Operational Research, Elsevier, vol. 317(3), pages 858-874.
    10. Duran-Mateluna, Cristian & Ales, Zacharie & Elloumi, Sourour, 2023. "An efficient benders decomposition for the p-median problem," European Journal of Operational Research, Elsevier, vol. 308(1), pages 84-96.
    11. Rebecca Stockbridge & Güzin Bayraksan, 2016. "Variance reduction in Monte Carlo sampling-based optimality gap estimators for two-stage stochastic linear programming," Computational Optimization and Applications, Springer, vol. 64(2), pages 407-431, June.
    12. Ouhimmou, Mustapha & Nourelfath, Mustapha & Bouchard, Mathieu & Bricha, Naji, 2019. "Design of robust distribution network under demand uncertainty: A case study in the pulp and paper," International Journal of Production Economics, Elsevier, vol. 218(C), pages 96-105.
    13. Ralf Krohn & Sven Müller & Knut Haase, 2021. "Preventive healthcare facility location planning with quality-conscious clients," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(1), pages 59-87, March.
    14. Huang, Mingzhong & He, Junliang & Yu, Hang & Yan, Wei & Tan, Caimao, 2024. "Improved Benders decomposition for stack-based yard template generation in an automated container terminal," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 188(C).
    15. Badri, Hossein & Fatemi Ghomi, S.M.T. & Hejazi, Taha-Hossein, 2017. "A two-stage stochastic programming approach for value-based closed-loop supply chain network design," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 105(C), pages 1-17.
    16. Zhouchun Huang & Qipeng P. Zheng & Andrew L. Liu, 2022. "A Nested Cross Decomposition Algorithm for Power System Capacity Expansion with Multiscale Uncertainties," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 1919-1939, July.
    17. Kayacık, Sezen Ece & Basciftci, Beste & Schrotenboer, Albert H. & Ursavas, Evrim, 2025. "Partially adaptive multistage stochastic programming," European Journal of Operational Research, Elsevier, vol. 321(1), pages 192-207.
    18. Teodor Gabriel Crainic & Mike Hewitt & Francesca Maggioni & Walter Rei, 2021. "Partial Benders Decomposition: General Methodology and Application to Stochastic Network Design," Transportation Science, INFORMS, vol. 55(2), pages 414-435, March.
    19. Kahr, Michael & Leitner, Markus & Ruthmair, Mario & Sinnl, Markus, 2021. "Benders decomposition for competitive influence maximization in (social) networks," Omega, Elsevier, vol. 100(C).
    20. Attari, Mahdi Yousefi Nejad & Torkayesh, Ali Ebadi, 2018. "Developing benders decomposition algorithm for a green supply chain network of mine industry: Case of Iranian mine industry," Operations Research Perspectives, Elsevier, vol. 5(C), pages 371-382.

    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:jglopt:v:91:y:2025:i:4:d:10.1007_s10898-025-01472-x. 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: 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.