View source for Chance-constraint method

Author: Cristine Li (ChE 345 Spring 2015)

Steward: Dajun Yue, Fengqi You

The '''chance-constrained method''' is one of the major approaches to solving optimization problems under various uncertainties. It is a formulation of an optimization problem that ensures that the probability of meeting a certain constraint is above a certain level. In other words, it restricts the feasible region so that the confidence level of the solution is high. The chance-constrained method is a relatively robust approach, however, it is often difficult to solve.<sup>1</sup>

Chance constrained optimization is especially important in engineering and finance where uncertainties in price, demand, supply, currency exchange rate, recycle and feed rate, and demographic condition are common. Some classical applications of the chance-constrained method include water reservoir management and financial risk management. More recently, the method has been used in unmanned autonomous vehicle navigation as well as optimal renewable energy generation.<sup>2</sup>

=Introduction=

Charnes and Cooper first introduced chance constrained programming in 1959 as a tool to solve optimization problems under uncertainty. They approached the problem by developing a method that ensured that the decision made by a model led to a certain probability of complying with constraints. Miller and Wagner, in 1965, revaluated the method and looked into how to increase the efficiency of solving chance constrained optimization problems. Many studies in the early 2000s, from Prekopa, Cooper, Deng, Herion, Romish, Nemirovski, Shapiro, etc have looked into more ways of analyzing chance constrained optimization and increasing the efficiencies of such problems. Recently, there has been a focus on using chance constrained optimization to solve process-engineering problems by Li, Garcia, and Wozny. Such problems are especially difficult due to their nonlinearity and dynamic processes.<sup>3</sup>

=Formulation=
In order to deal with uncertainties in optimization, the available stochastic information is integrated into the problem formulation. The general formulation of an optimization problem under uncertainty is 

<math>
\begin{align}
\text{min} & ~~ f(x,\xi)\\
\text{s.t} & ~~ g(x, \xi) = 0 \\
& ~~ h(x,\xi) \ge 0\\
\end{align}
</math>

where <math>f</math> is the objective function, <math>g</math> is the equality constraints, and <math>h</math> is the inequality constraints; <math>x</math> is the typical decision vector, and <math>\xi</math> is the vector of uncertainty. 

Under the chance constrained method, the inequality constraint is formulated as 

<math>P(h(x, \xi) \ge 0) \ge p</math> where <math>p \in [0,1] </math> is the probability level. 

In everyday engineering practices, the output variables <math>y</math> (which belongs to <math>x</math>) is typically restricted to 

<math>y_{min} \le y(\xi) \le y_{max}</math>

The upper and lower bound can be due to temperature and pressure restrictions and be very important for safety reasons.<sup>3</sup> This inequality constraint is then formulated as 

<math>P(y_{min} \le y(\xi) \le y_{max}) \ge p</math>. 

==Single vs Joint Chance Constraint==

Since both <math>h(x, \xi)</math> and <math>y(\xi)</math> are vectors, the actual constraints can be expanded out in two ways—individual and joint. A typical constraint is of the form

<math>h_i (x, \xi) \ge 0 (i = 1, ..., m)</math>

Under individual chance constraint, each line of the original constraint can be transformed individually. The above constraint would be expanded out to be 

<math>P (h_i (x, \xi) \ge 0) \ge p (i = 1, ..., m)</math>

With this transformation, each line is now its own chance constraint. They can be transformed into linear deterministic inequalities and analytical solutions can be obtained easily. 

With joint constraint, the original constraint as a whole, is reformulated as one chance constraint. 

<math>P(h_i (x, \xi) \ge 0 (i = 1,..., m)) \ge p</math> 

Individual chance constraints are easy to solve, however, they only guarantee that each line satisfies the constraint to a certain confidence level. Joint chance constraint ensures that the constraint as a whole is satisfied to a certain confidence level, however, it is incredibly difficult to solve, even numerically.<sup>4</sup>

=Approach to Solution=

In simple cases, where decision and random variables can be decoupled, and the constraint can be relaxed into '''deterministic constraints''' using probability density functions, and normal linear programming or nonlinear programming approaches can be used to solve the problem. <sup>5</sup> However, there are many challenges associated with transforming chance constraints into deterministic constraints, mainly associated with structure, convexity, and stability.<sup>4</sup>

In more complicated cases where decision and random variables can interact in a way such that it’s impossible to decouple them, the problem is currently impossible to solve. 

==Linear==

A problem is considered linear if linear transformation of multivariate distributed variables can be used to estimate the distribution of the constraints. The strategy to solving such a problem is to relax the problem into equivalent deterministic problems. In other words, one can calculate the probability by using the probability density function and substitute the left hand side of the constraint with a deterministic expression.

Typically, these probability density functions can be obtained through statistical regression if abundant data is available, or interpolation and extrapolation if few data is available. In cases where uncertain variables have correlations, marginal distribution functions can be used to calculate the probability.  

The feasible region of chance-constrained problems depends on the user’s desired confidence level. If a high confidence level is required, as in cases dealing with safety parameters, the feasible region is small. If the confidence level is lowered, the feasible region becomes larger. 

In certain cases where one constraint may be more important than another, one can formulate the problem such that the confidence level of one constraint is higher for the more important constraint.<sup>3</sup>

==Nonlinear==

Like the linear case, the strategy to solving a nonlinear chance constrained problem is to relax the problem by transforming it into a deterministic NLP problem. However, the nonlinear chance constrained problem is particularly difficult to solve because nonlinear propagation makes it hard to obtain the distribution of output variables even when the distributions of the variables with uncertainty are known. Several strategies, including back-mapping, robust optimization, and sample average approximation, are used to approximate the distribution of the output variables.

Dynamics nonlinear chance constrained problems have also been a focus of recent research. Such problems are even more difficult due to issues with stability.<sup>3</sup>

==Structural Challenges==
However, there are many complications to this simple approach. First off, simplifying the constraints into deterministic constraints may be very difficult due to difficulties associated with calculating the probabilities. For a nonlinear problem, for instance, the main challenge lies in holding the constraints and their gradients constant while calculating probabilities. Often, there is no closed-form analytical representation of the probabilities. Even numerical integration could be a huge problem in complex cases involving more than 3 dimensions.<sup>4</sup>

==Convexity Challenges==

Another challenge associated with transforming probabilistic constraints into deterministic ones has to do with '''global optimization'''. If a optimization problem is convex, then the local optimum is also the global optimum, otherwise, methods such as the McCormick Envelope approximation must be used. Consider a general chance constraint, <math>P(h(\xi \le x) \ge p) = F_{\xi} (h(x) \ge p)</math>. If <math>F_{\xi}(h(x))</math> is concave, then the optimization problem is convex.

In order to ensure that <math>F_{\xi}(h(x))</math> is concave, all <math>h</math> must be linear, <math>F_{\xi}(h(x))</math> must be increasing and concave. However, <math>F_{\xi}(h(x))</math> is never concave since 0 and 1 bound probability density functions. Many <math>F_{\xi}(h(x))</math> are '''log concave''', and it turns out that this property is enough for the overall problem to be considered convex. With convex problems, joint  chance constraints can be used to solved with convex algorithms such as the supporting hyperplane method.  For this reason and the importance of convexity in finding global optima, log concavity of different distributions must be considered in a chance constraint problem. 

A challenging issue comes in when the distribution is uniform or normal with independent components, since these may lack strong log concavity in certain circumstances. Furthermore, it should be noted that the Student’s t-distribution, the Cauchy distribution, the Pareto distribution, and the log-normal distribution are not log concave.<sup>4</sup>

==Stability Challenges==
Furthermore, calculating the probabilities require a probability density function. It is assumed that the probability density function is known or can be obtained for chance constraint problems. However, these functions are rarely ever known to be very precise, and are typically approximations. One issue that arises is if slight changes in the distribution could cause major changes to the optimal solution. If the assumed distribution was slightly different than the actual distribution, and the solution is not stable, then optimal solutions are useless and can lead to disastrous results. In order to achieve Hölder- or Lipschitz stability one has to impose further structural conditions, such as strong log-concavity, strict complementarity, and C1,1-differentiability.<sup>4</sup>

=Applications=

[[File:app1.png|frame|Chance-constrained method applications]]

The chance-constraint method is used very often in engineering as well as finance due to uncertainties in demand, supply, price, energy availability etc. 

Traditionally, chance-constraint method was very useful in '''power systems management'''. Uncertainties came in with energy availability. Sustainable energy such as wind and solar energy contained many uncertainties since wind speed differ significantly throughout the year and solar intensity can differ depending on time of the day or location. To ensure that a power plant can meet energy demand at least to a certain confidence level, chance-constraint method was formulated such that <math>P (h (x, \xi) \ge a ) \ge p</math> where <math>h(x, \xi)</math> represents the supply of energy under uncertainty, <math>a</math> represents the demand for energy, and <math>p</math> is the confidence level.<sup>2</sup>

Chance-constraint method has also often been used to meet '''safety requirements'''. For instance, the amount of rain that a certain area receives has huge uncertainties associated with it. Water reservoir have minimum and maximum levels at which no damage is done to the reservoir or the surrounding areas. In these cases, overestimation of uncertainty in combination with a high confidence level is used in the chance-constraint model to ensure that the probability of safety violation due to uncertainty in the amount of rain water received is as low as possible.<sup>1</sup>

Outside of engineering, the approach has been used for a long time in the financial industry for '''risk management'''. For instance, many uncertainties come in when investing. Market conditions are very unpredictable and volatile, so in order maximize the amount of money earned in return, one can utilize the chance constraint method and set the probability that one's investment return a specific value to be at a high confidence level.<sup>4</sup>
 
More recently, the approach has been applied to '''mid term supply chain planning at multiple sites'''. In other words, the production level at each site was determined by a chance-constraint model under demand uncertainty to avoid inventory depletion and excessive shortage on the consumers' end. This problem focused on the trade off between consumer satisfaction level and the production cost. In order to have high consumer satisfaction, a high confidence level is required for the constraint that supply satisfies consumer demands. However, this high confidence level correspond to high production cost. So the use of chance-constraint modeling allows a company to decide whether cost or consumer satisfaction is more important and then decide on the confidence level they want to meet.<sup>6</sup>

A state-of-the-art application of this model involves '''unmanned vehicles'''. In this problem, uncertainty comes in the form of random obstacles and sensor measurement errors. Probability density functions of these two variables are estimated based on previous data, and formulated into the chance constraints. Based on these constraints, unmanned vehicles can travel through a specific region with the shortest distance while avoiding random obstacles at a high confidence level.<sup>2</sup>

Another modern application involves '''fault tolerance and reliability of mechatronic systems'''. Industrial robots are becoming more and more common in factories. However, uncertainties are inherent in the performance of the robots and in the life-cycle of the robots.  Chance constraint modeling can be used to ensure a high performance level of the robots given uncertainties in the qualities of the different parts of the robots as well as in the construction of the robots.<sup>2</sup>

Overall, the chance-constraint method has many applications currently. Therefore, many have attempted to solve more complicated chance constraint problems involving nonlinear and dynamic random variables.

=Example=
The following example illustrates how to incorporate uncertainties into problem formulation in the financial industry. It will illustrate the difference between the deterministic and the chance-constraint model. 

Consider a pension fund that will be used by a company to issue payments for 15 years financed by buying three types of bonds. An initial fund of <math>K = 250000</math> is given. The objective of the problem is to maximize the amount of cash the company has, subject to the constraint of meeting the payment requirements each year. 

Let's define 

<math>\alpha_{ij} = </math> yield per bond of type <math>i</math> in year <math>j</math>

<math>\beta_{j} = </math> payment required in year <math>j</math>

<math>\gamma_i = </math> cost of bond <math>i</math>

<math>x_i = </math> number of bond <math>i</math> bought

Let's further define 

<math>a_{ij} = \sum_{k=1}^j \alpha_{ik} - \gamma_i</math>

<math>b_j= \sum_{k=1}^j  \beta_k -K</math>

==Deterministic==
For the deterministic model, the problem can be formulated as follow

<math>
\begin{align}
\text{max}  & ~~  \sum_{i=1}^n a_{im} x_i \\
\text{s.t.} & ~~  \sum_{i=1}^n a_{ij}x_i \ge b_j (j = 1,...,m) \\
\end{align}
</math>

The following data has been obtained

[[File:data.png|center]]

And a solution using linear programming found <math>x_1 = 31.1, x_2 = 55.5, x_3 = 147.3</math> and the final amount of cash is <math>$127332</math>

The thick line in the following graph shows year by year cash profile.

[[File:figa.png|center]]

Even though the thick line never goes below 0 in the previous graph. It's clear to see that with some uncertainty in the data, the line could easily dive below 0. 

Let's assume that <math>\beta_j</math> introduced above are expected values of random payments <math>\beta_{j*}</math>. We will further assume that <math>\beta_{j*}</math> is normally distributed with <math>\sigma = 500</math>. When 100 different payment profiles were simulated based on the normal distribution (represented by the thin gray lines) we can clearly see that it's actually possible for the cash to dive below 0 which shouldn't be allowed based on the constraint of the problem.<sup>4</sup>

==Individual Chance Constraint==
To incorporate uncertainty into this question, we will first look at the single chance constraint method. In this case, we will introduce a new variable

<math>\xi_j = \sum_{k=1}^j  \beta_{k*} -K </math>

The problem then becomes

<math>
\begin{align}
\text{max}  & ~~  \sum_{i=1}^n a_{im} x_i \\
\text{s.t.} & ~~  P(\sum_{i=1}^n a_{ij}x_i \ge \xi_j )\ge p) &~~ (j = 1,...,m) \\
\end{align}
</math>

Since we assumed that <math>\xi_j </math> is normally distributed with variance <math>\sigma^2</math>, we can transform the constraint for each <math>j</math> into 

<math>\sum_{i=1}^n a_{ij}x_i \ge b_j + \sigma_j q_p</math>

where <math>q_p</math> is the p-quantile of the standard normal distribution.

Selecting <math>p = 0.95</math>, we can solve the above problem as a deterministic linear programming problem, yielding <math>x_1 = 62.8, x_2 = 72.6, x_3 = 101.1</math> with final cash <math>$103925</math>.

So with uncertainties in the payment term, we should buy more short-term bonds. 

Now, using 100 normally distributed payment profiles, we arrive at the following graph. The probability of the cash profile going below <math>$0</math> is significantly lower than that of the deterministic model introduced above. 

[[File:figb.png|center]]

Based on the following graph, one can see that there's a trade-off between confidence level of always having a cash profile above <math>$0</math> and the final cash left in the company at the end of the 15 years. 

[[File:figc.png|center]]

Since individual chance constraint only makes sure that each line satisfies the constraint to a high confidence level, the entire profile could still dive below 0 at a less than ideal confidence level. This is a problem that could be addressed by joint chance constraint.<sup>4</sup>

==Joint Chance Constraint==
With joint chance constraint, the entire matrix of possible <math>\xi_j</math> is considered simultaneously. In other words, the problem is formulated as 

<math>
\begin{align}
\text{max}  & ~~  \sum_{i=1}^n a_{im} x_i \\
\text{s.t.} & ~~  P(\sum_{i=1}^n a_{ij}x_i \ge \xi_j  &~~ (j = 1,...,m) ) \ge p\\
\end{align}
</math>

This problem requires calculation of multidimensional distributions. Specific calculations are not included here because it's a very difficult process. In any case, the final answer obtained is <math>x1=65.8,   x2=83.7,   x3=86.2</math>,   with a final amount of cash of <math>$98,160</math>.<sup>4</sup>

Here, we see a further shift towards short term bonds and a lower cash return.

Note: All data and calculations are from Henrion's Introduction to Chance-Constraint Programming. Please consult the website for more information.<sup>4</sup>

=Conclusion=
The chance-constraint method is a great way to solve optimization problems due to its robustness. It allows one to set a desired confidence level and take into account trade-off between two or more objectives. However, it can be extremely difficult to solve. Probability density functions are often difficult to formulate, especially for the nonlinear problems. Issues with convexity and stability of these questions mean that small deviations from the actual density function could cause major changes in the optimal solution. Further complications are added when the variables with and without uncertainty can not be decoupled. Due to these complications, there's no single approach to solving chance-constraint problems. Though the most common approach to simple questions is to transform the chance constraints into deterministic functions by decoupling the variables with and without uncertainty and using probability density functions. 

This approach has many applications in the engineering field and the finance field. Namely, it is widely used in energy management, risk management, and more recently, determination of production level, performance of industrial robots, and performance of unmanned vehicle. A lot of research in the area focuses on solving nonlinear dynamic questions with chance constraints.

=References=
#  Ackoij, Wim et al. (2011). Chance Constrained Programming and Its Applications to Energy Management. ''Stochastic Optimization - Seeing the Optimal for the Uncertain.'' In-Tech. 
# Geletu, A. (2012). Chance constrained optimization-applications, properties and numerical issues. Retrieved May 24, 2015, from https://www.tu-ilmenau.de/fileadmin/media/simulation/Lehre/Vorlesungsskripte/Lecture_materials_Abebe/CCOPT_talk1.pdf
#Li, P., Garcia, H., & Gunter, W. (2008). Chance constrained programming approach to process optimization under uncertainty. ''Computer Aided Chemical Engineering,'' ''32''(1), 1245–1250. 
# Henrion, R. (2004). Introduction to Chance-Constrained Programming. Retrieved June 7, 2015, from http://stoprog.org/SPIntro/intro2ccp.php 
#Henrion, R. (2009). Chance Constrained Problems. Retrieved 7 June 2015, from http://stoprog.org/files/sp_XII_tutorials/Henrion.pdf
#Gupta, A., Maranas, C. D., & McDonald, C. M. (2000). Mid-term supply chain planning under demand uncertainty: customer demand satisfaction and inventory management. ''Computers & Chemical Engineering'', ''24'' (12), 2613–2621.