Source-linked AI summary
On Distributionally Robust Chance Constrained Programs with Wasserstein Distance
Weijun Xie
TL;DR
The paper addresses distributionally robust chance constrained programs under Wasserstein ambiguity, where uncertain constraints must hold with high probability across distributions near empirical data. It develops CVaR-based and mixed-integer reformulations, including a submodular big-M-free formulation for binary decisions, and reports promising computational performance. The approach relies on assumptions that can make the DRCC more conservative than the general setting.
Problem
The paper studies how to reformulate and approximate Wasserstein distributionally robust chance constrained programs while enforcing uncertain constraints uniformly over an ambiguity set.
Method
The paper derives deterministic and CVaR reformulations, bounded-region big-M mixed-integer representations, and a submodular big-M-free formulation with branch and cut for pure binary decisions.
Results
The formulations are reported as promising; CVaR solves the tested continuous instances quickly, while the binary big-M-free formulation substantially outperforms the big-M formulation in running time.
Takeaways & Limitations
The reformulations provide exact, inner, outer, and binary-specific solution approaches for Wasserstein DRCCPs across the settings studied.
Takeaways & Limitations
The ambiguity-set assumption may make the DRCC more conservative than the general setting, and the support is assumed to be a totally bounded Polish space.
Abstract
from arXiv · showhide
This paper studies a distributionally robust chance constrained program (DRCCP) with Wasserstein ambiguity set, where the uncertain constraints should be satisfied 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. We also 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 the submodular structure, we show that it admits a big-M free formulation, which can be solved by a branch and cut algorithm. Finally, we present a numerical study to illustrate the effectiveness of the proposed formulations.
1 Introduction
The paper studies Wasserstein-ambiguity distributionally robust chance constrained programs, seeking exact reformulations and tractable approximations. It develops CVaR-based, mixed-integer, and binary big-M-free formulations, supported by numerical evaluation.
- Problem setting: DRCCPs require simultaneous uncertain-constraint satisfaction with probability at least 1−ϵ for every distribution in the ambiguity set.The framework includes single and joint DRCCPs, with left-hand, right-hand, or two-sided uncertainty.
- Assumptions: The Wasserstein ambiguity set is built around a discrete empirical distribution generated by independent samples.The support is assumed to be a totally bounded Polish space, and the Wasserstein metric measures distance from the empirical distribution.
- Related literature: The paper addresses limited prior literature on DRCCPs with Wasserstein ambiguity sets, including strong NP-hardness results for optimizing over the associated feasible set.Existing work includes reformulations and CVaR approximations under related settings.
- Contributions: The paper derives a deterministic reformulation with a CVaR interpretation, enabling inner and outer approximations whose strengths are compared.The reformulation is presented for the feasible set induced by the distributionally robust chance constraint.
- Contributions: Once the feasible region is bounded, the DRCCP admits a mixed-integer representation using big-M coefficients and additional binary variables.The resulting representation is described as a mixed integer conic program.
- Contributions: For pure binary decisions, submodular structure yields a big-M-free mixed-integer linear reformulation solvable with a branch and cut algorithm.The nonlinear reformulation constraints are recast as submodular knapsack constraints before exploiting their polyhedral properties.
2 Exact Reformulations
The paper first converts the Wasserstein DRCC feasible set into a deterministic and CVaR-based representation. It then establishes mixed-integer representations, including a bounded-region big-M formulation and a specialized binary formulation.
- Deterministic reformulation: The deterministic reformulation uses strong duality, indicator-function decomposition, and reciprocal dual-variable substitution.These are identified as the three steps in the proof strategy.
- CVaR reformulation: The feasible set has a CVaR interpretation, and the subsequent inner and outer approximations are based mainly on this formulation.The paper introduces VaR and CVaR before stating the equivalent CVaR-constrained representation.
- Mixed-integer reformulation: The general feasible set is decomposed into a potentially nonconvex set and a convex set, with the second component depending on the uncertainty type.For left-hand uncertainty, the second set can contain x = 0 under stated conditions; for right-hand or two-sided uncertainty, it is empty.
- Mixed-integer reformulation: When the relevant set is bounded, nonlinear constraints can be represented as mixed-integer constraints using big-M coefficients and binary variables.The formulation introduces N binary variables; the big-M linearization uses binary and continuous auxiliaries.
- Binary DRCCP: For pure binary decisions, the nonlinear constraints become submodular knapsack constraints, enabling a big-M-free formulation without additional binary variables.The paper proposes solving this formulation with a branch and cut algorithm.
- Right-hand uncertainty: For right-hand uncertainty, the representation is more compact because it avoids the disjunction and the additional positive variable ν.A mixed-integer representation is also derived for this special case.
3 Outer and Inner Approximations
The paper develops one outer and three inner approximations of the Wasserstein DRCC feasible set, using exact reformulations to balance bounds, feasibility, and tractability. These approximations form inclusion hierarchies and converge to the exact set under empirical-distribution convergence conditions.
- Overview: The outer approximation provides a lower bound, while the inner approximations provide feasible solutions and can outperform the exact mixed integer model on large instances.The numerical study is stated to demonstrate this combined advantage, particularly for large-sized instances.
- Outer approximation: The VaR-based set ZVaR is an outer approximation of the DRCC feasible set and can be interpreted as a deterministic counterpart of an infinity-Wasserstein DRCC.Its formulation uses a regular chance constrained program with the discrete empirical distribution and a dual-norm penalty on uncertain constraints.
- Inner approximation I: The robust scenario set ZR is an inner approximation obtained by enforcing sampled constraints with an added δϵ∥a(x)∥∗ penalty.The penalty is described as a robustification of the scenario approach, especially when the sample size is below the usual threshold.
- Inner approximation II: The second inner approximation ZI is constructed through a feasible γ and can be optimized by enumerating ⌈Nϵ⌉ candidate values of α.For each α, the resulting chance constraint is mixed integer representable; under exponential empirical convergence, ZI converges almost surely to Z.
- Approximation hierarchy: The approximations satisfy ZI ⊆ Z ⊆ ZVaR for every N, while both ZI and ZVaR converge to Z as N grows.The robust scenario approximation is also contained in the CVaR-based inner approximation: ZR ⊆ ZCVaR.
- CVaR approximation: When ϵ ≤ 1/N, the DRCC feasible set is convex and exactly equals its CVaR approximation ZCVaR.The paper also establishes ZR ⊆ ZCVaR, so the robust scenario approximation is at least as conservative.
4 DRCCP with Pure Binary Decision Variables
For pure binary decisions, the paper exploits submodularity to replace nonlinear DRCC constraints with submodular knapsack constraints. Extended polymatroid inequalities then yield a big-M-free mixed integer formulation that can be handled by branch and cut.
- Binary DRCCP: For binary DRCCPs, the paper improves earlier reformulations by exploiting the structure of decision variables x ∈ {0,1}^n.The stronger formulation development is based on polyhedral results for submodular functions.
- Submodular polyhedra: A submodular function over binary variables has an epigraph whose convex hull is characterized by extended polymatroid inequalities.Although there are n! inequalities, a violated inequality can be separated by sorting coordinates in descending order, in O(n log n) time.
- Big-M-free formulation: The nonlinear constraints are recast as submodular knapsack constraints, producing a big-M-free mixed integer representation of S ∩ Z.The construction replaces the relevant constraints by convex hulls of submodular epigraphs described through extended polymatroid inequalities.
- Set representation: The binary feasible region decomposes as S ∩ Z = (S ∩ bZ1) ∪ (S ∩ Z2), enabling the final mixed integer formulation.The decomposition follows the paper’s representation of Z as Z1 ∪ Z2.
- Algorithm: The resulting optimization problem can be solved by branch and cut using separation over the most violated submodular epigraphs.At each node, the method identifies a selected number of most violated epigraphs and adds valid inequalities generated by separation.
5 Numerical Demonstration
Numerical studies on continuous and binary DRMKP instances compare exact, inner, outer, CVaR, and big-M-free formulations, and use cross validation to select Wasserstein radii. The approximations generally produce near-optimal or improved solutions, while the big-M-free model substantially reduces runtime.
- Experimental setup: The study used Gurobi 7.5 with default settings, a 3600-second time limit, and random instances generated under specified uniform distributions.
- Continuous DRMKP: 10 random continuous DRMKP instances with n = 20 and I = 10 tested exact, VaR, CVaR, and ICCP formulations using N ∈{100, 1000} samples.
- Continuous DRMKP: All models reached optimality within 2 minutes for N = 100; CVaR solved each instance within a second, while ICCP nearly recovered the true optimum.VaR was usually 2-3% and CVaR 1-2% from true optimality.
- Continuous DRMKP: For N = 1000, CVaR solved to optimality within 2 seconds, while the other models exceeded the time limit; ICCP gave the best feasible solutions.VaR provided better upper bounds and closed more than 10% of the optimality gap on average compared with BigM.
- Wasserstein-radius selection: Cross validation showed that properly chosen Wasserstein radii reduced violation probabilities below ϵ = 0.05 while preserving objective values close to the regular chance-constrained model.The best radius did not systematically increase or decrease with correlation and was positively correlated with the regular model’s 90-percentile violation.
- Binary DRMKP: BigM-free formulations solved almost all binary DRMKP instances within 10 minutes, whereas most BigM instances reached the time limit.The big-M-free model uses O(n) binary and O(N) continuous variables, compared with O(N + n) and O(N × I) for BigM.
6 Conclusion
The paper develops reformulations and approximations for Wasserstein distributionally robust chance constrained programs, including a big-M-free approach for binary decisions. Numerical studies find the proposed formulations promising.
- A DRCCP admits a CVaR-constrained reformulation and therefore tight inner and outer approximations.
- When the feasible region is bounded, a DRCCP is mixed integer representable with big-M coefficients and additional binary variables.
- For binary DRCCPs, the paper proposes a big-M-free formulation and a branch-and-cut solution algorithm.
- Numerical studies demonstrate that the proposed formulations are promising.