PaperlayerView exact revision on arXiv

Source-linked AI summary

Data-Driven Chance Constrained Programs over Wasserstein Balls

Zhi Chen, Daniel Kuhn, Wolfram Wiesemann

arXiv:1809.00210v3math.OC

TL;DR

Data-driven chance constraints have largely been studied with φ-divergence ambiguity sets, whose shared-support restriction can be problematic with limited samples or high dimension. This paper gives exact mixed-integer conic reformulations over Wasserstein balls, with mixed-integer linear forms for the 1- and ∞-norms; the introduction also reports that φ-divergence sets may underestimate true VaR in low-sample regimes.

  • Problem

    Data-driven chance constraints have focused mainly on φ-divergence ambiguity sets, which exclude distributions assigning positive probability to outcomes absent from the empirical support.

    Source: §1 · p. 3

  • Method

    The paper derives deterministic reformulations for individual and joint chance constraints over Wasserstein balls as mixed-integer conic programs.

    Source: §1 · p. 5

  • Results

    In low-sample regimes, φ-divergence ambiguity sets may underestimate the true VaR with high probability, while Figure 1 compares their best-case reliability with Wasserstein worst-case reliability.

    Source: §1 · p. 4

  • Takeaways & Limitations

    For Wasserstein balls using the 1- or ∞-norm, the reformulations reduce to mixed-integer linear programs.

    Source: §1 · p. 5

    When an optimal reformulation solution has A^T x = b and a^T x ≥ b, the original chance constraint requires a^T x < b, motivating a variant with an additional constraint.

    Source: §2.3 · p. 13

Abstract

from arXiv · show

We provide an exact deterministic reformulation for data-driven chance constrained programs over Wasserstein balls. For individual chance constraints as well as joint chance constraints with right-hand side uncertainty, our reformulation amounts to a mixed-integer conic program. In the special case of a Wasserstein ball with the $1$-norm or the $\infty$-norm, the cone is the nonnegative orthant, and the chance constrained program can be reformulated as a mixed-integer linear program. Our reformulation compares favourably to several state-of-the-art data-driven optimization schemes in our numerical experiments.

1. Introduction

The introduction motivates Wasserstein ambiguity sets as a response to limitations of φ-divergence sets in data-driven chance constraints, then presents exact deterministic reformulations for individual and joint constraints. The reformulations are mixed-integer conic programs, with linear formulations for the 1- and ∞-norms.

1. Introduction

  • φ-divergence ambiguity sets require distributions to share the empirical distribution’s support, which is problematic with large dimension or few training samples.They also compare distributions scenario by scenario and may violate symmetry and the triangle inequality.Source: §1 · p. 3
  • In low-sample regimes, φ-divergence ambiguity sets may underestimate the true VaR with high probability, unlike the worst-case reliability offered by Wasserstein sets.Figure 1 compares these reliability bounds for a uniform distribution on [0,1].Source: Figure 1 · p. 4, §1 · p. 4
  • For the worst-case VaR under a Wasserstein ball, the introduction gives a lower bound on reliability; for φ-divergence balls, it gives an upper bound.The φ-divergence upper bound holds for every ball radius.Source: §1 · p. 4
  • Earlier work on Wasserstein chance constraints established hardness for covering problems and proposed a bicriteria approximation that trades a higher risk threshold for a smaller optimality gap.Its guarantee weakens as the selected threshold approaches the original risk threshold.Source: §1 · p. 5
  • The paper derives deterministic reformulations for individual chance constraints and joint chance constraints with right-hand-side uncertainty as mixed-integer conic programs.For the 1- or ∞-norm, the cone is the nonnegative orthant and the programs reduce to mixed-integer linear programs.Source: §1 · p. 5
  • The reformulations use structural insights into worst-case distributions rather than duality and are largely independent of the Wasserstein ball’s ground metric.The cited prior reformulations require disjoint random-variable subvectors across joint safety conditions.Source: §1 · p. 5

2. Exact Reformulation of Data-Driven Chance Constraints

The section derives an exact deterministic test for Wasserstein-robust chance constraints from the transportation cost of moving training samples into unsafe scenarios. It then specializes the test to individual and joint chance constraints, yielding mixed-integer conic formulations.

2.1. Uncertainty Quantification over Wasserstein Balls

  • The worst-case distribution greedily transports already-unsafe samples and then the nearest safe samples, partially moving the last sample when the transportation budget runs out.Samples farther from the unsafe set remain unchanged.Source: §2.1 · p. 7

2.2. Reformulation of Generic Chance Constraints

  • A decision satisfies the generic Wasserstein chance constraint exactly when the εN smallest sample-to-unsafe-set distances sum to at least θN.The sum is the minimum cost of moving a fraction ε of the training samples into the unsafe set.Source: §2.2 · p. 8, Wasserstein ambiguity set (1) is… · p. 8

Wasserstein ambiguity set (1) is equivalent to the deterministic inequality

  • The partial-sum condition is convex in the decision-dependent distances and admits an LP representation, enabling an exact deterministic reformulation without enumerating sample subsets.Theorem 3 substitutes this representation into the original chance-constrained program.Source: Wasserstein ambiguity set (1) is… · pp. 10–11

2.3. Reformulation of Individual Chance Constraints

  • Individual affine chance constraints admit an equivalent mixed-integer conic formulation, with binary variables encoding the positive-part terms.The formulation assumes A^T x ≠ b over X; the paper states this condition does not restrict generality and gives a 2K + 1-problem procedure for a boundary case.Source: §2.3 · pp. 12–13
  • For individual constraints, the conic formulation becomes linear under the 1-norm or ∞-norm, and a second-order cone program under rational p-norms with p > 1.The reformulation adds N + 1 continuous decisions and N constraints relative to the classical chance-constrained formulation.Source: §2.3 · p. 13

2.4. Reformulation of Joint Chance Constraints with Right-Hand Side Uncertainty

  • For joint chance constraints with right-hand-side uncertainty, a closed-form distance to the unsafe set yields an equivalent mixed-integer conic program.Its distributionally robust formulation adds N + 1 continuous decisions and N linear constraints relative to the classical formulation.Source: §2.4 · pp. 14–15

3. Numerical Experiments

The experiments assess computational scalability and out-of-sample performance of the reformulation on portfolio and transportation problems. In transportation tests, the ambiguous formulations meet the target risk threshold, unlike the classical formulation, while often incurring modestly higher costs.

3. Numerical Experiments

  • The experiments compare the exact reformulation with a bicriteria approximation for portfolios and with classical and φ-divergence-based formulations for transportation.The study examines computational scalability and out-of-sample performance in a data-driven setting.Source: §3 · p. 15, §3.1 · p. 16, §3.2 · p. 21

3.1. Portfolio Optimization

  • The bicriteria approximation scheme produces higher-cost solutions and is more computationally expensive than the exact reformulation in the portfolio comparison.The comparison covers combinations of risk threshold ε and Wasserstein radius θ.Source: §3.1 · p. 16, Table 1 · p. 16
  • For larger sample sizes N, under (ε,θ) = (0.10,0.05), the bicriteria approximation scheme is faster than our exact reformulation in the reported experiments.Figure 4 reports runtimes and reciprocal runtime ratios; shaded regions span the 5% to 95% quantiles over 50 randomly generated instances, while solid lines show medians.Source: §3.1 · p. 17, Figure 4 · p. 17

3.2. Transportation

  • In the transportation instance, each safety condition has one random variable with coefficient 1 on the right-hand side, so the exact reformulation is a mixed-integer linear program for any norm.The study also evaluates scalability over varying numbers of distribution centers, training samples, and Wasserstein radii.Source: §3.2 · p. 18
  • For the smallest Wasserstein radius, the ambiguous transportation program is harder to solve than the classical program, but it becomes considerably easier at larger radii.The feasible binary-vector set shrinks monotonically with θ, and the feasible region tends to convexify as θ increases.Source: §3.2 · p. 18, Table 2 · p. 19, Table 3 · p. 19
  • The classical formulation significantly violates the chance constraint, while both ambiguous formulations meet the target risk threshold, often at modestly higher transportation costs.The Wasserstein approach appears to yield lower costs than the φ-divergence approach, especially when data is scarce.Source: Figure 7 · p. 20, Figure 8 · p. 21, Figure 9 · p. 21

A. Distance to a Union of Halfspaces

This section derives a closed-form expression for the distance from a point to a union of finitely many closed halfspaces. It also uses strong conic duality in the single-halfspace proof.

A. Distance to a Union of Halfspaces

Loading 1809.00210v3…