15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 juillet 2017

15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 juillet 2017

Horaire Auteurs Mon horaire

Plenary III

14 juil. 2017 12h00 – 13h00

Salle: Amphithéâtre Banque Nationale

Présidée par Miguel F. Anjos

1 présentation

  • 12h00 - 13h00

    Approximations of Chance Constraints

    • Shabbir Ahmed, prés., School of Industrial and Systems Engineering, Georgia Institute of Technology

    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.

Retour