Chance Constraints

Chance Constraints

Docs

Product

Support

Chance constraints

In the previous sections we assumed that each constraint with uncertain data was satisfied with probability 1. In many situations, however, such a requirement may lead to solutions that over-emphasize the worst-case. In such cases, it is more natural to require that a candidate solution has to satisfy a constraint with uncertain data for “nearly all” realizations of the uncertain data. More specifically, in this approach one requires that the robust solution has to satisfy the constraint with probability at least \(1 - \epsilon\), where \(\epsilon \in [0,1]\) is a pre-specified small tolerance. Instead of the deterministic constraint

\[a^T x \le b\]

we now require that the chance constraint

\[\text{Prob} \left(x : a(\xi)^T x \le b \right) \geq 1 - \epsilon\]

be satisfied, where the probability is associated with the specific distribution of the uncertain parameter(s) \(\xi\).

Approximation

In general, (linear) problems with chance constraints are very hard to solve even if the probability distribution of the uncertain data is completely known. It is, however, possible to construct safe tractable approximations of chance constraints using robust optimization (see, for instance, Chapter 2 of [BTGN09]). The way a chance constraint is approximated depends merely on the general characteristics of the data distribution, rather than on precise specification of the distribution. If more information is available about the distribution, this will generally result in a tighter approximation. A tighter approximation, however, could result in a more difficult solution process (for instance, requiring second-order cone programming instead of just linear programming).

Chance constraints in AIMMS

The procedure to introduce chance constraints into your robust optimization model is as follows:

indicate which parameters in your model should become random, and specify the properties of their distributions, and
specify which constraints should be considered chance constraints, and specify their probability and method of approximation.

Random parameters

A probability distribution is modeled in AIMMS as a numeric Parameter for which the Random property has been set (see also Parameter Declaration and Attributes). If the property Random is set, AIMMS will create the mandatory Distribution attribute for this parameter which must be used to specify the characteristics of the distribution to be used for that parameter. All random parameters for which a distribution has been specified are considered to be independent.

Example

Consider the following declaration

Parameter Demand {
    IndexDomain  : i;
    Property     : Random;
    Distribution : Bounded(Demand(i).level,0.1);
}

This declaration states that parameter Demand corresponds to a bounded probability distribution with a mean equal to the nominal value of Demand and a support of 0.1.

Supported distributions

AIMMS supports the distribution types listed in Table 52

Table 52 Supported distribution types for robust optimization
Distribution	Meaning
\({\texttt{Bounded}}(m,s)\)	mean \(m\) with range \([m-s,m+s]\)
\({\texttt{Bounded}}(m,l,u)\)	range \([l,u]\) and mean \(m\) not in the center of the range
\({\texttt{Bounded}}(m_l,m_u,l,u)\)	range \([l,u]\) and mean in interval \([m_l,m_u]\)
\({\texttt{Bounded}}(m_l,m_u,l,u,v)\)	range \([l,u]\) and mean in interval \([m_l,m_u]\), and variance bounded by \(v\)
\({\texttt{Unimodal}}(c,s)\)	unimodal around \(c\) with range \([c-s,c+s]\)
\({\texttt{Symmetric}}(c,s)\)	symmetric around \(c\) with range \([c-s,c+s]\)
\({\texttt{Symmetric}}(c,s,v)\)	symmetric around \(c\) with range \([c-s,c+s]\), and variance bounded by \(v\)
\({\texttt{Support}}(l,u)\)	range \([l,u]\) (and no information about the mean)
\({\texttt{Gaussian}}(m_l,m_u,v)\)	Gaussian with mean in interval \([m_l,m_u]\) and variance bounded by \(v\)

All distributions in this table are bounded except the Gaussian distribution. The distributions \({\texttt{Bounded}}(m_l,m_u,l,u)\), \({\texttt{Bounded}}(m_l,m_u,l,u,v)\) and \({\texttt{Symmetric}}(c,s,v)\) are currently not implemented.

Symmetric unimodal distribution

A distribution is called unimodal if its density function is monotonically increasing up to a certain point \(c\) and monotonically decreasing afterwards. For symmetric distribution AIMMS offers the possibility to mark it as unimodal by using the unimodal keyword:

Parameter Demand {
    IndexDomain  : i;
    Property     : Random;
    Distribution : Symmetric(Demand(i).level,0.1), unimodal;
}

The unimodal keyword can only be used in combination with a symmetric distribution.

Linear relation

In addition to specifying a random parameter using an independent distribution, AIMMS also allows you to define a random parameter as a linear combination of other random parameters (but not as combination of uncertain parameters). For example,

Parameter Demand {
    Property     : Random;
    Distribution : Sum( i, xi(i) );
}

where xi is an random parameter. To avoid cyclic definitions, AIMMS requires that the distributions of random parameters cannot be specified as an expression of other random parameters which are themselves defined as an expression of random parameters.

Chance constraints

A constraint in your mathematical program becomes a chance constraint in the context of robust optimization by setting its Chance property. The definition of a chance constraint may only contain random parameters, normal parameters and variables. Uncertain parameters are not allowed inside a chance constraint. When setting the Chance property for a constraint, you must specify two new attributes for the constraint, the Probability attribute and the Approximation attribute. It is allowed to use chance constraints in a mixed-integer program.

The Probability attribute

The Probability attribute specifies the probability with which the chance constraint should be satisfied when solving a robust optimization model. The value of the Probability attribute should be a numerical expression in the range \([0,1]\). If the probability is 0, then AIMMS will not generate the chance constraint. If the probability is 1, then AIMMS will generate an uncertainty constraint.

The Approximation attribute

The Approximation attribute is used to define the approximation that should be used to approximate the chance constraint. Its value should be an element expression into the predefined set AllChanceApproximationTypes.

Supported approximation types

The approximations supported by AIMMS are:

Ball,
Box,
Ball-box,
Budgeted, and
Automatic.

A detailed mathematical definition of these approximation types can be found in Chapter 2 of [BTGN09]. Whether or not a particular approximation type is possible, depends on the characteristics of the distributions used in the chance constraint, as explained below. By specifying approximation type Automatic the most accurate approximation possible will be used. In some cases it might be beneficial to use a less tight approximation because it leads to a robust counterpart that is easier to solve.

Example

Consider the declaration

Constraint ChanceConstraint {
    IndexDomain   : i;
    Property      : Chance;
    Definition    : Demand(i) * X(i) <= 10;
    Probability   : prob(i);
    Approximation : 'Ball';
}

This declaration states that ChanceConstraint is a chance constraint with probability prob(i), and that approximation type Ball is used to approximate the chance constraint.

Possible approximations per distribution

this table shows for each (supported) distribution which approximation types are possible. It also shows whether the approximation will result in a linear or a second-order cone robust counterpart.

Table 53 Allowed approximations and their resulting problem type
Distribution	Automatic	Ball	Box	Ball-box	Budgeted
\({\texttt{Bounded}}(m,s)\)	linear	conic	linear	conic	linear
\({\texttt{Bounded}}(m,l,u)\)	conic		linear
\({\texttt{Unimodal}}(c,s)\)	conic		linear
\({\texttt{Symmetric}}(c,s)\) (unimodal)	conic	conic	linear	conic	linear
\({\texttt{Support}}(l,u)\)	linear		linear
\({\texttt{Gaussian}}(m_l,m_u,v)\)	conic

For the \({\texttt{Bounded}}(m,s)\) distribution the automatic approximation equals the Budgeted approximation, and the automatic approximation of the \({\texttt{Support}}(l,u)\) distribution equals the Box approximation. The non-unimodal \({\texttt{Symmetric}}(c,s)\) distribution is treated as a \({\texttt{Bounded}}(m,s)\) distribution.

Combining distributions

A chance constraint cannot contain both bounded random parameters and Gaussian random parameters. Different types of bounded random parameters can be combined, in which case only a part of the available information will be used. The possible combinations of bounded random parameters are given in this table.

Explanation

If a random parameter with a \({\texttt{Bounded}}(m,l,u)\) distribution and a random parameter with a \({\texttt{Support}}(l,u)\) distribution are used in a single chance constraint, then this table states that the \({\texttt{Bounded}}(m,l,u))\) distribution of the first random parameter will be treated as a \({\texttt{Support}}(l,u)\) distribution. Unimodal distributions can only be mixed with unimodal \({\texttt{Symmetric}}(c,s)\) and \({\texttt{Support}}(l,u)\) distributions.

\({\texttt{Bounded}}(m,s)\)

\({\texttt{Bounded}}(m,l,u)\)

\({\texttt{Unimodal}}(c,s)\)

\({\texttt{Symmetric}}(c,s)\) (unimodal)

\({\texttt{Support}}(l,u)\)