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.

References in corpus (2)

• Maximizing Influence in Social Networks: A Two-Stage Stochastic Programming Approach That Exploits Submodularity
• A Polyhedral Study of the Static Probabilistic Lot-Sizing Problem

Cited by in corpus (6)

• Chance-Constrained Set Covering with Wasserstein Ambiguity
• An Exact Cutting Plane Method for $k$-submodular Function Maximization
• Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints
• Efficient presolving methods for the influence maximization problem
• A Polyhedral Approach to Bisubmodular Function Minimization
• An Exact Method for Constrained Maximization of the Conditional Value-at-Risk of a Class of Stochastic Submodular Functions