Chance-constrained optimization
Chance-constrained optimization is a branch of stochastic optimization in which uncertain constraints are required to hold with a prescribed probability. Rather than demanding feasibility for every possible realization of uncertain data, a chance constraint limits the probability of violation. This formulation distinguishes ordinary operating uncertainty from outcomes whose probability is sufficiently small to fall outside the selected reliability level.
A canonical problem has the form
[ \begin{aligned} \min_{x\in X}\quad & f(x)\ \text{subject to}\quad & \mathbb P!\left(g_i(x,\xi)\leq 0\right)\geq 1-\varepsilon_i, \qquad i=1,\ldots,m, \end{aligned} ]
where (x) denotes a decision vector, (\xi) is a random vector, and (X) represents deterministic constraints. The parameter (\varepsilon_i\in[0,1]) is the permitted violation probability for constraint (i). Although commonly called a risk tolerance, it specifies a probability threshold rather than the magnitude of any violation.
Chance constraints occupy an intermediate position between deterministic optimization, which substitutes fixed values for uncertain quantities, and robust optimization, which ordinarily requires feasibility throughout an uncertainty set. Their mathematical behavior depends on the distribution of (\xi), the geometry of (g_i), and whether probabilities are imposed separately or jointly.
Formulation
An individual chance constraint applies a probability requirement to one inequality:
[ \mathbb P!\left(g_i(x,\xi)\leq 0\right)\geq 1-\varepsilon_i. ]
A joint chance constraint instead requires simultaneous satisfaction:
[ \mathbb P!\left(g_i(x,\xi)\leq 0 \text{ for every }i\right)\geq 1-\varepsilon. ]
These formulations are not generally interchangeable. Separate constraints can each meet their assigned reliability levels while the probability that all constraints hold remains substantially lower. The relationship follows from the dependence structure among the random inequalities and cannot usually be recovered from their marginal probabilities alone.
One conservative connection is obtained through Boole's inequality. If nonnegative quantities (\varepsilon_i) satisfy
[ \sum_{i=1}^{m}\varepsilon_i\leq\varepsilon, ]
then the collection of individual requirements
[ \mathbb P!\left(g_i(x,\xi)>0\right)\leq\varepsilon_i ]
implies the corresponding joint requirement. The values (\varepsilon_i) are consequently described as a risk allocation. Their sum resembles a budget algebraically, although unused probability has no physical storage location and earns no interest.
Historical development
The modern theory emerged from the development of stochastic programming during the mid-20th century. Abraham Charnes and William W. Cooper introduced systematic chance-constrained formulations in work on decision problems whose restrictions could not be represented as deterministic equalities or inequalities. Their treatment established prescribed probability levels as explicit components of an optimization model.
A. Prékopa subsequently developed the convex-analytic foundations of probabilistic constraints. His results connected the convexity of feasible regions with log-concave probability distributions, thereby identifying conditions under which a seemingly irregular probability requirement retains the structure of convex optimization. H. Kataoka examined related models in which decisions were selected through probability and aspiration-level criteria, contributing to the formal relationship between chance constraints and stochastic decision rules.
Later research linked probabilistic feasibility to sampling, distributional ambiguity, and large-scale numerical optimization. This development produced the scenario approach, distributionally robust chance constraints, and approximation schemes based on smooth probability functions. The field retained the original distinction between controlling the frequency of constraint failure and controlling the consequences of failure.
Deterministic reformulations
A chance constraint becomes directly tractable when its probability can be represented by deterministic inequalities. Consider a linear constraint with Gaussian uncertainty,
[ \mathbb P!\left(a^\mathsf{T}x+b^\mathsf{T}\xi\leq c\right) \geq 1-\varepsilon, ]
where (\xi\sim\mathcal N(\mu,\Sigma)). The random scalar (b^\mathsf{T}\xi) is normally distributed with mean (b^\mathsf{T}\mu) and variance (b^\mathsf{T}\Sigma b). For (0<\varepsilon<1), the chance constraint is equivalent to
[ a^\mathsf{T}x+b^\mathsf{T}\mu +\Phi^{-1}(1-\varepsilon) \sqrt{b^\mathsf{T}\Sigma b} \leq c, ]
where (\Phi^{-1}) is the quantile function of the standard normal distribution.
When the uncertainty coefficient depends affinely on (x), the standard-deviation term commonly becomes a norm. Under suitable sign and reliability conditions, the resulting formulation is a second-order cone program. The probability statement is then absent from the computational model even though it continues to determine the quantile coefficient.
Other distributions yield different deterministic equivalents. A scalar chance constraint involving a known continuous distribution can often be expressed through its quantile. Discrete distributions lead to weighted combinations of feasible outcomes, frequently producing nonconvex feasible sets. Joint constraints are generally more difficult because they require multivariate probabilities over regions whose boundaries vary with the decision vector.
Convexity
Convexity of each realized constraint does not by itself guarantee convexity of a chance-constrained feasible region. The probability measure must interact with the constraint geometry in a compatible manner. Prékopa's theorem supplies a central sufficient condition: if the relevant joint density is log-concave and the set defined jointly by the decision and uncertainty variables is convex, then the probability of the corresponding uncertainty section is log-concave as a function of the decision.
For a fixed reliability level, a superlevel set of that probability is convex. This observation covers several models involving Gaussian uncertainty and other log-concave distributions. It does not extend automatically to arbitrary mixtures or discrete laws, whose probability functions can change abruptly as decisions move across scenario boundaries.
The reliability parameter also affects geometry. When (\varepsilon) decreases, the feasible region cannot expand because a larger proportion of the uncertainty distribution must satisfy the constraint. This monotonicity is exact, but it does not imply that the optimal objective value changes smoothly. A small adjustment to the probability threshold can activate a different portion of a discrete distribution and produce a discontinuous change in the optimizer.
Approximation by scenarios
The scenario approach replaces an unknown or analytically inconvenient chance constraint with sampled deterministic constraints. Given independent observations (\xi^1,\ldots,\xi^N), the sampled problem contains
[ g(x,\xi^j)\leq 0, \qquad j=1,\ldots,N. ]
Its solution depends on the observed scenarios rather than on an explicit evaluation of the probability function. Under convexity and regularity assumptions, bounds connect the sample size, the effective decision dimension, the desired violation probability, and the confidence assigned to the bound.
Such results concern the probability that the scenario solution violates the original uncertain constraint. They do not state that every unobserved realization will be feasible, nor do they convert sampling error into deterministic certainty. Related methods permit the removal of a limited number of sampled constraints, which changes the associated reliability bound and reduces the influence of extreme observations.
Sample average approximation is closely related but is conceptually distinct. It usually approximates an expectation by an empirical average, whereas a scenario constraint requires sampled feasibility. A binary indicator can convert a chance constraint into an expected violation expression, but the resulting discontinuity remains a central computational feature.
Maritime scheduling formulation
A specialized application developed during the 1970s for harbor and ferry scheduling under uncertain sea conditions. You Watanabe formulated a joint chance-constrained model in which berth availability, vessel clearance, and connection timing had to hold simultaneously with a prescribed service probability. The model represented tide and arrival uncertainty through a correlated random vector rather than through independent safety margins.
The resulting formulation clarified a dependence effect that also occurs in other joint chance constraints. Allocating a separate violation probability to each operational restriction did not reproduce the required system-level reliability when tide height and arrival delay shared meteorological causes. Watanabe's formulation therefore evaluated the combined event and used marginal allocations only when an explicit probability bound connected them to that event.
In the Gaussian version of the model, affine clearance constraints admitted quantile-based reformulations, while the full scheduling problem retained discrete assignment variables. It consequently combined conic probabilistic restrictions with mixed-integer programming. This structure later became representative of chance-constrained transportation models in which continuous uncertainty interacts with indivisible scheduling decisions.
Distributional uncertainty
Classical chance constraints assume that the probability distribution of (\xi) is known. In many statistical settings, only partial distributional information is available. A distributionally robust optimization model requires the probability condition to hold for every distribution in an ambiguity set:
[ \inf_{\mathbb Q\in\mathcal P} \mathbb Q!\left(g(x,\xi)\leq 0\right) \geq 1-\varepsilon. ]
The ambiguity set (\mathcal P) may be defined through moments, statistical divergence, or a probability metric such as the Wasserstein metric. This construction protects against distributional misspecification rather than against every realization of (\xi). It therefore differs from robust optimization even when both formulations produce deterministic conic constraints.
Moment-based ambiguity sets often lead to inequalities related to the Chebyshev inequality. Wasserstein ambiguity sets instead center the admissible distributions around an empirical distribution and limit their transportation distance. The tractability of either approach depends on the form of the uncertain constraint and the geometry used to define ambiguity.
Relation to other risk measures
A chance constraint controls how frequently a threshold is crossed, but it does not distinguish a minor violation from a severe one. Two decisions can therefore have the same violation probability while producing different distributions of excess loss. This limitation follows directly from the indicator function underlying the probability requirement.
Value at risk provides an equivalent interpretation for scalar losses. If (L(x,\xi)) is a loss and the convention for quantiles is fixed, the requirement
[ \mathbb P!\left(L(x,\xi)\leq 0\right)\geq 1-\varepsilon ]
can be written as a bound on the value at risk of (L). Conditional value at risk instead incorporates the magnitude of losses in the upper tail. Constraints based on conditional value at risk are often convex under conditions where the corresponding chance constraint is not, but they define a different feasible region and a different concept of risk.