.png){kind=icon}
返回
Chance-constrained set multicover problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2026.07.038.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们考虑一个带有不确定参数的集合覆盖问题的变体，我们称之为机会约束集合多重覆盖问题（CC-SMCP）。在该问题中，我们假设存在关于所选集合能否覆盖某项的不确定性，目标是在给定概率下确定一个最小成本的集合组合，使每个项目i至少被覆盖ki次。为解决CC-SMCP，我们采用枚举组合学、离散概率分布和组合优化的技术，推导出具有界限层次的精确等价确定性重构，并开发相应的外逼近（OA）算法。此外，我们考虑通过向量支配关系减少机会约束的数量，并利用对数变换方法和二项分布性质重构CC-SMCP的两个特例。关于基于采样的方法的理论结果，即样本平均近似（SAA）方法和重要性采样（IS）方法，也被研究用于在有限离散概率空间下近似CC-SMCP的真实最优值。我们的数值实验证明了所提出的OA方法的有效性，特别是在概率矩阵稀疏的场景中，大多数情况下优于基于采样的方法，并验证了我们解决方案的实际适用性。
Keyword:
Integer programming
Set multicover problem
Chance-constrained optimization
