ALSO-X#: better convex approximations for distributionally robust chance constrained programs

This paper studies distributionally robust chance constrained programs (DRCCPs), where the uncertain constraints must be satisfied with at least a probability of a prespecified threshold for all probability distributions from the Wasserstein ambiguity set. As DRCCPs are often nonconvex and some DRCCPs may not have mixed-integer reformulations, researchers have been developing various convex inner approximations. Recently, ALSO-X has been proven to outperform the conditional value-at-risk (CVaR) approximation of a regular chance constrained program when the deterministic set is convex. In this work, we relax this assumption by introducing a new ALSO-X# method to solve DRCCPs. Namely, in the bilevel structures of ALSO-X and CVaR approximation, we observe that the lower-level ALSO-X is a special case of the lower-level CVaR approximation, and the upper-level CVaR approximation is more restricted than the one in ALSO-X. This observation motivates us to propose ALSO-X#, which has a bilevel structure—in the lower-level problem, we adopt the more general CVaR approximation, and for the upper-level one, we choose the less restricted ALSO-X. We show that ALSO-X# is always better than CVaR approximation and can outperform ALSO-X under regular chance constrained programs and type ∞-Wasserstein ambiguity set. We also provide new sufficient conditions under which ALSO-X# outputs an optimal solution to a DRCCP. We apply ALSO-X# to a wireless communication problem and numerically demonstrate that the solution quality can be even better than the exact method. © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2024.