Probabilistic partial set covering with an oracle for chance constraints

Hao-Hsiang Wu, Simge Kucukyavuz*

*Corresponding author for this work

研究成果: Article同行評審

3 引文 斯高帕斯(Scopus)

摘要

We consider a class of chance-constrained combinatorial optimization problems, which we refer to as probabilistic partial set-covering (PPSC) problems. Given a prespecified risk level 2 [0; 1], the PPSC problem aims to find the minimum cost selection of subsets of items such that a target number of items is covered with probability at least 1. We show that PPSC admits an efficient probability oracle that computes the coverage probability exactly, under certain distributions of the random variables representing the coverage relation. Using this oracle, we give a compact mixed-integer program that solves the PPSC problem for a special case. For large-scale instances for which an exact oracle-based method exhibits slow convergence, we propose a samplingbased approach that exploits the special structure of PPSC. The oracle can be used as a tool for checking and fixing the feasibility of the solution given by this approach. In particular, we introduce a new class of facet-defining inequalities for a submodular substructure of PPSC, and show that a sampling-based algorithm coupled with the probability oracle effectively provides high-quality feasible solutions to the large-scale test instances.

原文English
頁(從 - 到)690-718
頁數29
期刊SIAM Journal on Optimization
29
發行號1
DOIs
出版狀態Published - 1 一月 2019

指紋 深入研究「Probabilistic partial set covering with an oracle for chance constraints」主題。共同形成了獨特的指紋。

引用此