Towards Large-Scale Probabilistic Set Covering Problems: An Efficient Benders Decomposition Approach

In this paper, we investigate the probabilistic set covering problem (PSCP) in which the right-hand side is a binary random vector and the covering constraint is required to be satisfied with a prespecified probability. We consider the case with a finite discrete distribution of the random vector, which usually arises in the context of the sample average approximation approach. We develop an effective Benders decomposition (BD) algorithm for solving large-scale PSCPs that enjoys two key advantages: (i) the number of variables in the underlying Benders reformulation is independent of the scenario size, and (ii) the Benders cuts can be separated by an efficient combinatorial algorithm. For the special case that the random vector is a combination of several independent random blocks/subvectors, we explicitly take this kind of block structure into consideration and develop a more efficient BD algorithm. Moreover, to further speed up the two proposed BD algorithms, we develop a class of strong valid inequalities, which are guaranteed to be facet-defining for the polytope induced by the probabilistic constraint. Numerical results on instances with up to one million scenarios demonstrate the effectiveness of the proposed BD algorithms over a black box mixed integer programming solver’s branch-and-cut and automatic BD algorithms and a state-of-the-art algorithm in the literature.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.

Funding: The work of Wei-Kun Chen was supported by the National Natural Science Foundation of China (NSFC) [Grant 12571317], the work of Yu-Hong Dai was supported by the NSFC [Grant 92473208], and the work of Wei Lv was supported in part by the NSFC [Grant 12331011].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1307) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1307). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.