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.
Citation
Working Paper
Article
View Bicriteria Approximation of Chance Constrained Covering Problems