Stochastic red-blue set covering: a decomposition approach

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.