Robust reformulations of ambiguous chance constraints with discrete probability distributions

Abstract

This paper proposes robust reformulations of ambiguous chance constraintswhen the underlying family of distributions is discrete and supported in aso-called “p-box” or “p-ellipsoidal” uncertainty set. Using the robust opti-mization paradigm, the deterministic counterparts of the ambiguous chanceconstraints are reformulated as mixed-integer programming problems whichcan be tackled by commercial solvers for moderate sized instances. For largersized instances, we propose a safe approximation algorithm that is compu-tationally efficient and yields high quality solutions. The associated approachand the algorithm can be easily extended to joint chance constraints, nonlinearinequalities, and dependent data without introducing additional mathemati-cal optimization complexity to that of the original robust reformulation. Innumerical experiments, we first present our approach over a toy-sized chanceconstrained knapsack problem. Then, we compare optimality and computa-tional performances of the safe approximation algorithm with those of the ex-act and the randomized approaches for larger sized instances via Monte Carlosimulation.