Strengthened and Faster Linear Approximation to Joint Chance Constraints with Wasserstein Ambiguity

Many real-world decision-making problems in energy systems, transportation, and finance have uncertain parameters in constraints. Wasserstein distributionally robust joint chance constraints (WDRJCC) offer a promising solution by explicitly guaranteeing the probability of the simultaneous satisfaction of multiple constraints. However, WDRJCC are computationally demanding, and practical applications often require more tractable approaches, especially for large-scale and complex problems, such as power system unit commitment problems and multilevel problems with chance constraints in lower levels. To address this, this paper proposes a novel convex inner approximation for WDRJCC with right-hand side uncertainties. Motivated by the strengthening process that leads to a faster but still exact mixed-integer reformulation, we propose a strengthened and faster linear approximation (SFLA) by strengthening an existing convex inner approximation. This strengthening process reduces the number of constraints and tightens the feasible region for ancillary variables, leading to significant computational speedup. We prove that the proposed SFLA does not introduce additional conservativeness and can even be less conservative compared with common approximations such as worst case conditional value at risk (W-CVaR). We then extend the proposed SFLA to robustness maximization, a decision-making paradigm that can be more interpretable, in which the risk level and the Wasserstein radius are determined by maximizing solution robustness subject to a utility degradation limit. We discuss the connection between risk minimization and radius maximization as two formulations of robustness maximization and show the advantage of radius maximization. In power system unit commitment, the proposed SFLA achieves up to $10\times$ and on average $3.8\times$ computational speedup compared with the strengthened and exact mixed-integer reformulation in finding comparable high-quality solutions. In a bilevel strategic bidding problem in which the exact reformulation is not applicable because of nonconvexity, the proposed SFLA can lead to $90\times$ speedup compared with existing convex approximation methods including W-CVaR. In robustness maximization, the proposed SFLA demonstrated more than $100\times$ speedup than other convex approximations.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.

Funding: This paper was supported by the Engineering and Physical Sciences Research Council (EPSRC) [Grant EP/W027321/1]. Y. Zhou’s and Y. Xia’s works were also supported by the Engineering Studentship from the University of Edinburgh. H. Yang’s work is funded by the National Natural Science Foundation of China under [Grants 72201232 and 72231008], Guangdong Provincial Key Laboratory of Mathematical Foundations for Artificial Intelligence (2023B1212010001), and Shenzhen Key Laboratory of Crowd Intelligence Empowered Low-Carbon Energy Network, China (project number ZDSYS20220606100601002).

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.1073) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.1073). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.