Title: Chance-Constrained Combinatorial Optimization with a Probability Oracle and Its Application to Probabilistic Partial Set Covering,
Abstract: We investigate a class of chance-constrained combinatorial optimization
problems. Given a pre-specified risk level $\epsilon \in [0,1]$, the
chance-constrained program aims to find the minimum cost selection of a vector
of binary decisions $x$ such that a desirable event $\mathcal{B}(x)$ occurs
with probability at least $ 1-\epsilon$. In this paper, we assume that we have
an oracle that computes $\mathbb P( \mathcal{B}(x))$ exactly. Using this
oracle, we propose a general exact method for solving the chance-constrained
problem. In addition, we show that if the chance-constrained program is solved
approximately by a sampling-based approach, then the oracle can be used as a
tool for checking and fixing the feasibility of the optimal solution given by
this approach. We demonstrate the effectiveness of our proposed methods on a
variant of the probabilistic set covering problem (PSC), which admits an
efficient probability oracle. We give a compact mixed-integer program that
solves PSC optimally (without sampling) for a special case. For large-scale
instances for which the exact methods exhibit slow convergence, we propose a
sampling-based approach that exploits the special structure of PSC. In
particular, we introduce a new class of facet-defining inequalities for a
submodular substructure of PSC, and show that a sampling-based algorithm
coupled with the probability oracle solves the large-scale test instances
effectively.