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

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

Plenary III

Jul 14, 2017 12:00 PM – 01:00 PM

Location: Amphithéâtre Banque Nationale

Chaired by Miguel F. Anjos

1 Presentation

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    12:00 PM - 01:00 PM

    Approximations of Chance Constraints

    • Shabbir Ahmed, presenter, 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.