Optimization Online


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

Javiera Barrera(javiera.barrera***at***uai.cl)
Tito Homem-de-Mello(tito.hmello***at***uai.cl)
Eduardo Moreno(eduardo.moreno***at***uai.cl)
Bernardo K. Pagnoncelli(bernardo.pagnoncelli***at***uai.cl)
Gianpiero Canessa(gianpiero.canessa***at***uai.cl)

Abstract: We study chance-constrained problems in which the constraints involve the probability of a rare event. We discuss the relevance of such problems and show that the existing sampling-based algorithms cannot be applied directly in this case, since they require an impractical number of samples to yield reasonable solutions. Using a Sample Average Approximation (SAA) approach combined with importance sampling (IS) techniques, we show how variance can be reduced uniformly over a suitable approximation of the feasibility set, and as a result the problem can be solved with much fewer samples. We provide sufficient conditions to obtain such uniform variance reduction and prove asymptotic convergence of the combined SAA-IS approach. We apply our methodology to a telecommunications problem, find IS distributions that satisfy the conditions laid out for uniform variance reduction in that context and present numerical results to illustrate the ideas.

Keywords: Chance-constrained programming, Sample Average Approximation, Importance sampling, Rare-event simulation

Category 1: Stochastic Programming

Citation: Universidad Adolfo IbaƱez, Feb 2014.

Download: [PDF]

Entry Submitted: 02/26/2014
Entry Accepted: 02/26/2014
Entry Last Modified: 02/26/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society