Chance Constraints

332. Chance Constraints

Constraints required to hold with high probability rather than always. Useful when:

Always-feasibility is too expensive
The data is uncertain and 100% reliability isn’t needed (or even possible)
Service-level requirements are stated probabilistically (“95% of orders shipped on time”)

332.1. Formulation

For uncertain parameters $𝜉$ :

𝑃 ({𝑎 (𝜉)}^{𝑇} 𝑥 \leq 𝑏 (𝜉)) \geq 1 - 𝛼

The constraint ${𝑎 (𝜉)}^{𝑇} 𝑥 \leq 𝑏 (𝜉)$ must hold with probability at least $1 - 𝛼$ . $𝛼$ is the risk level — typically $𝛼 = 0.05$ or $0.01$ .

Equivalent: violate the constraint with probability at most $𝛼$ .

332.2. Joint vs individual chance constraints

Individual: each constraint $𝑖$ holds with high probability, separately:

𝑃 (𝑎_{𝑖}^{𝑇} 𝑥 \leq 𝑏_{𝑖}) \geq 1 - 𝛼_{𝑖}, \forall 𝑖

Joint: all constraints hold simultaneously with high probability:

𝑃 (𝑎_{𝑖}^{𝑇} 𝑥 \leq 𝑏_{𝑖}, \forall 𝑖) \geq 1 - 𝛼

Joint is stronger — and harder to handle. Often individual is what’s actually intended.

332.3. Reformulation under normality

If $𝑎^{𝑇} 𝑥 - 𝑏$ is normally distributed (with mean $𝜇 (𝑥)$ and variance $𝜎^{2} (𝑥)$ ):

𝑃 (𝑎^{𝑇} 𝑥 \leq 𝑏) = Φ (\frac{𝑏 - 𝜇 (𝑥)}{𝜎 (𝑥)}) \geq 1 - 𝛼

\Rightarrow 𝜇 (𝑥) + Φ^{- 1} (1 - 𝛼) 𝜎 (𝑥) \leq 𝑏

The chance constraint becomes a deterministic constraint involving $𝜎 (𝑥)$ — possibly convex (e.g., if $𝜎 (𝑥)$ is linear in $𝑥$ and $𝛼 \leq 0.5$ ). This is a second-order cone constraint, solvable by interior-point methods.

332.4. Reformulation via sampling

Without normality, use scenarios $𝜉^{1}, \dots, 𝜉^{𝑁}$ :

𝑃 ({{𝑎 (𝜉)}^{𝑇} 𝑥 \leq 𝑏 (𝜉)}) \approx \frac{1}{𝑁} | {𝑠 : {𝑎 (𝜉^{𝑠})}^{𝑇} 𝑥 \leq 𝑏 (𝜉^{𝑠})} |

Enforcing the chance constraint $\geq 1 - 𝛼$ on the sample becomes an MILP with binary indicators per scenario — exponential growth, manageable up to $𝑁 \approx 1000$ .

332.5. Equivalence to VaR / CVaR

In risk management, chance constraints relate to:

Value at Risk (VaR): the $(1 - 𝛼)$ -quantile of the loss distribution. The chance constraint $𝑃 (loss \leq 𝑉) \geq 1 - 𝛼$ is essentially $𝑉 \geq {VaR}_{𝛼}$ .
Conditional VaR (CVaR): expected loss beyond VaR. Tighter, convex, easier to optimize.

In practice, CVaR-based reformulations of chance constraints are more numerically tractable.

332.6. Where chance constraints matter

Service-level inventory: 95% in-stock probability per cycle
Robust facility location: feasible under high-probability demand realizations
Portfolio optimization: $𝑃 (loss \geq 𝑉) \leq 𝛼$
Power systems: probabilistic generation-load balance
Network design: links carry expected traffic with high probability

332.7. See also

Stochastic Programming
Two-stage Recourse
SAA
Cycle Service Level — inventory application