1 Presentation

• 
  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.