Stochastic red-blue set covering: a decomposition approach

David Islip () and Roy H. Kwon ()
Additional contact information
David Islip: University of Toronto
Roy H. Kwon: University of Toronto

Journal of Global Optimization, 2025, vol. 91, issue 4, No 9, 923-951

Abstract: 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.

Keywords: Combinatorial optimization; Two-stage stochastic programming; Mixed binary programming; Branch-and-cut (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-025-01472-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:91:y:2025:i:4:d:10.1007_s10898-025-01472-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-025-01472-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().