.png){kind=icon}
Return
Chance-constrained set multicover problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2026.07.038.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider a variant of the set covering problem with uncertain parameters, which we refer to as the chance-constrained set multicover problem (CC-SMCP). In this problem, we assume 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 that covers each item i at least ki times with a prescribed probability. To tackle CC-SMCP, we employ techniques of enumerative combinatorics, discrete probability distributions, and combinatorial optimization to derive exact equivalent deterministic reformulations that feature a hierarchy of bounds, and develop the corresponding outer-approximation (OA) algorithm. Additionally, we consider reducing the number of chance constraints via vector dominance relations and reformulate two special cases of CC-SMCP using the log-transformation method and binomial distribution properties. Theoretical results on sampling-based methods, i.e., the sample average approximation (SAA) method and the importance sampling (IS) method, are also studied to approximate the true optimal value of CC-SMCP under a finite discrete probability space. Our numerical experiments demonstrate the effectiveness of the proposed OA method, particularly in scenarios with sparse probability matrices, outperforming sampling-based approaches in most cases and validating the practical applicability of our solution approaches.
Keywords:
Integer programming
Set multicover problem
Chance-constrained optimization
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
Organization
Cited Papers
No cited papers available