Optimization Online


Bicriteria Approximation of Chance Constrained Covering Problems

Weijun Xie (wxie***at***vt.edu)
Shabbir Ahmed (sahmed***at***isye.gatech.edu)

Abstract: A chance constrained optimization problem involves constraints with random data which can be violated with probability bounded above by a prespecified small risk parameter. Such constraints are used to model reliability requirements in a variety of application areas such as finance, energy, service and manufacturing. Except under very special conditions, chance constrained problems are extremely difficult. There has been a great deal of elegant work on developing tractable approximations of chance constraints. Unfortunately none of these approaches come with any theoretical performance guarantees. We prove that such guarantees are impossible by providing an inapproximability result. On the other hand, for a large class of chance constrained problems involving covering type constraints we propose a bicriteria approximation scheme. Our scheme finds a solution whose violation probability may be larger than, but is within a constant factor of, the specified risk parameter and whose objective value is within a constant factor of the true optimal value. Key to our developments is the construction of a tractable convex relaxation of a chance constrained problem and an appropriate scaling of a solution to this relaxation. We extend our approximation results to the setting when the underlying distribution of the constraint data is not known. That is, we consider distributionally robust chance constrained covering problems with convex moment and Wasserstein ambiguity sets, and provide bicriteria approximation results.

Keywords: Chance constrained problem; approximation algorithm; distributionally robust; relaxation

Category 1: Stochastic Programming

Category 2: Robust Optimization

Category 3: Combinatorial Optimization

Citation: Working Paper

Download: [PDF]

Entry Submitted: 01/07/2018
Entry Accepted: 01/08/2018
Entry Last Modified: 01/08/2018

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