Chance-constrained problems and rare events: an importance sampling approach (Q291054)

The authors consider chance-constrained optimization problems with rare events, that is, problems in which the violation probability is very small, e.g. \(10^{-6}\). They propose an integration of SAA (sample average approximation approach) with importance sampling (IS), a technique widely used in simulation to estimate probabilities of rare events. Also, they give sufficient conditions to obtain a uniform variance reduction, and prove asymptotic convergence of the combined SAA-IS approach. The authors describe in detail the telecommunication problem with Bernoulli input distributions and present explicit mixed integer programming formulations for the rare-event chance-constrained problem with importance sampling. In the last part of the paper numerical results are presented and concluding remarks are discussed.