15th EUROPT Workshop on Advances in Continuous Optimization
Montréal, Canada, July 12 — 14, 2017
15th EUROPT Workshop on Advances in Continuous Optimization
Montréal, Canada, July 12 — 14, 2017
Plenary III
Jul 14, 2017 12:00 PM – 01:00 PM
Location: Amphithéâtre Banque Nationale
Chaired by Miguel F. Anjos
1 Presentation

12:00 PM  01:00 PM
Approximations of Chance Constraints
A chance constrained optimization problem involves random constraints that are required to be satisfied with a prespecified probability. 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 constraints impart severe nonconvexities making the optimization problem 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 show that by relaxing the required probability level by a little bit we can indeed provide a constant factor approximation algorithm. We further extend these results to distributionally robust chance constraints, where the probability distribution of the random constraint data is not fully specified. Key to our developments is the construction of a tractable convex relaxation and an appropriate scaling of the solution to the relaxation.