On Distributionally Robust Chance Constrained Program with Wasserstein Distance

Abstract

This paper studies a distributionally robust chance constrained program (DRCCP) with Wasserstein ambiguity set, where the uncertain constraints should satisfy with a probability at least a given threshold for all the probability distributions of the uncertain parameters within a chosen Wasserstein distance from an empirical distribution. In this work, we investigate equivalent reformulations and approximations of such problems. We first show that a DRCCP can be reformulated as a conditional-value-at-risk constrained optimization problem, and thus admits tight inner and outer approximations. When the metric space of uncertain parameters is a normed vector space, we show that a DRCCP of bounded feasible region is mixed integer representable by introducing big-M coefficients and additional binary variables. For a DRCCP with pure binary decision variables, by exploring submodular structure, we show that it admits a big-M free formulation and can be solved by branch and cut algorithm. This result can be generalized to mixed integer DRCCPs. Finally, we present a numerical study to illustrate effectiveness of the proposed methods.