Chance constrained programming was
developed as a means of describing constraints in mathematical
programming models in the form of probability levels of attainment.
1
Consideration of chance constraints allows decision makers to
consider mathematical programming objectives in terms of the
probability of their attainment. If α is a predetermined confidence
level desired by a decision maker, the implication is that a
constraint will be violated at most (1−α) of all possible
cases.
Chance constraints are thus special
types of constraints in mathematical programming models, where
there is some objective to be optimized subject to constraints. A
typical mathematical programming formulation might be:
The objective function f(X) can be profit, with the function
consisting of n variables
X as the quantities of
products produced and f(X)
including profit contribution rate constants. There can be any
number m of constraints in
Ax, each limited by some
constant b. Chance
constraints can be included in Ax, leading to a number of possible
chance constraint model forms. Charnes and Cooper presented three
formulations 2 :
Any coefficient of this model (Y, A, b) may be probabilistic. The intent of
this formulation would be to maximize (or minimize) a function
while assuring α
probability that a constraint is met. While the expected value of a
function usually involves a linear functional form, chance
constraints will usually be nonlinear. This formulation would be
appropriate for many problems seeking maximum profit subject to
staying within resource constraints at some specified probability.
The intent is to accomplish some functional performance level while
satisfying the chance constraint set. This formulation might be
used in identifying portfolio investments with minimum variance,
which often is used as a measure of risk.
This formulation is generally much more difficult to accomplish,
especially in the presence of joint chance constraints (where
simultaneous satisfaction of chance constraints is required). The
only practical means to do this is running a series of models
seeking the highest α level
yielding a feasible solution.
All three models include a common
general chance constraint set, allowing probabilistic attainment of
functional levels:
This set is nonlinear, requiring nonlinear programming solution.
This inhibits the size of the model to be analyzed, as large values
of model parameters m
(number of constraints) and especially n (number of variables) make it much
harder to obtain a solution.
Most chance constrained applications
assume normal distributions for model coefficients. Goicoechea and
Duckstein presented deterministic equivalents for non-normal
distributions. 3 However, in general, chance
constrained models become much more difficult to solve if the
variance of parameter estimates increases (the feasible region
shrinks drastically when more dispersed distributions are used).
The same is true if α is
set at too high a value (for the same reason—the feasible region
shrinks).
Chance constrained applications also
usually assume coefficient independence. This is often appropriate.
However, it is not appropriate in many investment analyses.
Covariance elements of coefficient estimates can be incorporated
within chance constraints, eliminating the need to assume
coefficient independence. However, this requires significantly more
data, and vastly complicates model data entry.
Chance Constrained Applications
Chance constrained models are not
nearly as widespread as linear programming models. A number of
applications involve financial planning, to include retirement fund
planning models. 4 Chance constraints have also been
applied to stress testing value-at-risk (and CVaR). 5 Beyond
financial planning, chance constrained models have been applied to
supplier selection 6 in operations, as well as in
project selection in construction. 7 A
multi-attribute model for selection of infrastructure projects in
an aerospace firm seeking to maximize company performance subject
to probabilistic budget constraints has been presented.
8
There are green chance constrained models seeking efficient climate
policies considering available investment streams and renewable
energy technologies. 9
Portfolio Selection
Assume a given sum of money to be
invested in n possible securities. We denote by
x = (x1,…, xn) is an investment
proportion vector (also called a portfolio). As for the number of
securities n, many large institutions have “approved lists” where n
is anywhere from several hundred to a thousand. When attempting to
form a portfolio to mimic a large broad based index (like
S&P500, EAFE, Wilshire 5000), n can be up to several thousand.
Denote by
r i the percent return of
i-th security;Other
objectives to characterize the i-th security could be
-
s i is social responsibility of i-th security
-
g i is growth in sales of i-th security
-
a i is amount invested in R&D of i-th security
-
d i is dividends of i-th security
-
q i is liquidity of i-th security
Consideration of such investment
objectives will lead to utilization of multi-objective programming
models. The investor tries to select several possible securities
from the n securities to
maximize his profit, which leads to the investor’s decision problem
as:
(1)
where
-
r p is percent return on a portfolio over the holding period.
-
Ax ≤ b, the feasible region in decision space
In the investor’s decision problem
(1), the
quantity r p to
be maximized is a random variable because r p is a function of the
individual-security r
i random variables. Therefore, (1) is a stochastic programming problem.
Stochastic programming models are similar to deterministic
optimization problems where the parameters are known only within
certain bounds but take advantage of the fact that probability
distributions governing the data are known or can be estimated. To
solve a stochastic programming problem, we need convert the
stochastic programming to an equivalent deterministic programming problem. A
popular way of doing this is to use utility function U(∙)], which maps stochastic terms into
their deterministic equivalents. For example, by use of the means
μ i, variances
σ ii and
covariances σ ij
of the r i, a
portfolio selection problem is to maximize expected utility.
where λ ≥ 0 a risk
reversion coefficient and may be different from different
investors. In other words, a portfolio selection problem can be
modeled by a trade-off between the mean and variance of random
variable r p:
Assuming [U(r p)] is Taylor series
expandable, the validity of E[U(r p)] and thus the above
problem can be guaranteed if [U(r p)] Taylor series
expandable of r = (r 1,…, r n) follows the multinormal
distribution. Another alternative to Markowitz’s mean variance
framework, chance constrained programming was employed to model the
portfolio selection problem. We will demonstrate the utilization of
chance constrained programming to model the portfolio selection
problem in the next section.
Demonstration of Chance Constrained Programming
The following example was taken from
Lee and Olson (2006). 12 The Hal Chase Investment Planning
Agency is in business to help investors optimize their return from
investment, to include consideration of risk. Through the use of
nonlinear programming models, Hal Chase can control risk.
Hal deals with three investment
mediums: a stock fund, a bond fund, and his own Sports and Casino
Investment Plan (SCIP). The stock fund is a mutual fund investing
in openly traded stocks. The bond fund focuses on the bond market,
which has a much stabler return, although significantly lower
expected return. SCIP is a high-risk scheme, often resulting in
heavy losses, but occasionally coming through with spectacular
gains. In fact, Hal takes a strong interest in SCIP, personally
studying investment opportunities and placing investments daily.
The return on these mediums, as well as their variance and
correlation, are given in Table 7.1:
Table
7.1
Hal chase investment data
Stock S
|
Bond B
|
SCIP G
|
|
---|---|---|---|
Average return
|
0.148
|
0.060
|
0.152
|
Variance
|
0.014697
|
0.000155
|
0.160791
|
Covariance with S
|
0.000468
|
−0.002222
|
|
Covariance with B
|
−0.000227
|
Note that there is a predictable
relationship between the relative performance of the investment
opportunities, so the covariance terms report the tendency of
investments to do better or worse given that another investment did
better or worse. This indicates that variables S and B tend to go up and down together
(although with a fairly weak relationship), while variable
G tends to move opposite to
the other two investment opportunities.
Hal can develop a mathematical
programming model to reflect an investor’s desire to avoid risk.
Hal assumes that return on investments are normally distributed
around the average returns reported above. He bases this on
painstaking research he has done with these three investment
opportunities.
Maximize Expected Value of Probabilistic Function
Using this form, the objective is to
maximize return:
subject to staying within budget:
having a probability of positive
return greater than a specified probability:
with all variables greater than or
equal to 0:
The solution will depend on the
confidence limit α. Using EXCEL, and varying α from 0.5, 0.8, 0.9
and 0.95, we obtain the solutions given in Table 7.2:
Table
7.2
Results for chance constrained formulation
(1)
Probability
{return ≥ 0}
|
α
|
Stock
|
Bond
|
Gamble
|
Expected return
|
---|---|---|---|---|---|
0.50
|
0
|
–
|
–
|
1000.00
|
152.00
|
0.80
|
0.253
|
379.91
|
–
|
620.09
|
150.48
|
0.90
|
0.842
|
556.75
|
–
|
443.25
|
149.77
|
0.95
|
1.282
|
622.18
|
–
|
377.82
|
149.51
|
0.99
|
2.054
|
668.92
|
–
|
331.08
|
149.32
|
The probability determines the penalty
function α. At a probability of 0.80, the one-tailed normal
z-function is 0.253, and thus the chance constrained is:
The only difference in the constraint
set for the different rows of Table 7.2 is that α is varied.
The affect is seen is that investment is shifted from the high risk
gamble to a bit safer stock. The stock return has low enough
variance to assure the specified probabilities given. Had it been
higher, the even safer bond would have entered into the solution at
higher specified probability levels.
Minimize Variance
With this chance constrained form, Hal
is risk averse. He wants to minimize risk subject to attaining a
prescribed level of gain. The variance-covariance matrix measures
risk in one form, and Hal wants to minimize this function.
This function can be constrained to
reflect other restrictions on the decision. For instance, there
typically is some budget of available capital to invest.
Finally, Hal only wants to minimize
variance given that he attains a prescribed expected return. Hal
wants to explore four expected return levels: $50/$1000 invested,
$100/$1000 invested, $150/$1000 invested, and $200/$1000 invested.
Note that these four levels reflect expected returns of 5, 10, 15,
and 20 %.
Solution Procedure
The EXCEL input file will start off
with the objective, MIN followed by the list of variables. Then we
include the constraint set. The constraints can be stated as you
want, but the partial derivatives of the variables need to consider
each constraint stated in less-than-or-equal-to form. Therefore,
the original model is transformed to:
The solution for each of the four gain
levels are given in Table 7.3:
Table
7.3
Results for chance constrained formulation
(2)
Specified Gain
|
Variance
|
Stock
|
Bond
|
Gamble
|
---|---|---|---|---|
≥50
|
106.00
|
–
|
825.30
|
3.17
|
≥100
|
2928.51
|
406.31
|
547.55
|
46.14
|
≥150
|
42,761
|
500.00
|
–
|
500.00
|
≥152
|
160,791
|
–
|
–
|
1000.00
|
The first solution indicates that the
lowest variance with an expected return of $50 per $1000 invested
would be to invest $825.30 in B (the bond fund), $3.17 in G (the risky alternative), and keeping
the 171.53 slack. The variance is $106.002. This will yield an
average return of 5 % on the money invested. Increasing
specified gain to $100 yields the designed expected return of $100
with a variance of $2928.51. Raising expected gain to 150 yields
the prescribed $150 with a variance of $42,761.06. Clearly this is
a high risk solution. But it also is near the maximum expected
return (if all $1000 was placed on the riskiest alternative,
G, the expected return would
be maximized at $152 per $1000 invested). A model specifying a gain
of $200 yields an infeasible solution, and thus by running multiple
models, we can identify the maximum gain available (matching the
linear programming model without chance constraints). It can easily
be seen that lower variance is obtained by investing in bonds, then
shifting to stocks, and finally to the high-risk gamble
option.
Maximize Probability of Satisfying Chance Constraint
The third chance constrained form is
implicitly attained by using the first form example above, stepping
up α until the model becomes infeasible. When the probability of
satisfying the chance constraint was set too high, a null solution
was generated (don’t invest anything—keep all the $1000). Table
7.4 shows
solutions obtained, with the highest α yielding a solution being
4.8, associated with a probability very close to 1.0 (0.999999
according to EXCEL).
Table
7.4
Results for chance constrained formulation
(3)
α
|
Stock
|
Bond
|
Gamble
|
Expected return
|
---|---|---|---|---|
3
|
157.84
|
821.59
|
20.57
|
75.78
|
4
|
73.21
|
914.93
|
11.86
|
67.53
|
4.5
|
406.31
|
547.55
|
46.14
|
64.17
|
4.8
|
500.00
|
–
|
500.00
|
61.48
|
4.9 and up
|
–
|
–
|
–
|
0
|
Real Stock Data
To check the validity of the ideas
presented, we took real stock data from the Internet, taking daily
stock prices for six dispersed, large firms, as well as the
S&P500 index. Data was manipulated to obtain daily rates of
return over the period 1999 through 2008 (2639
observations—dividing closing price by closing price of prior day).
where V t = return for day
t and V t − 1 = return for the
prior day. (The arithmetic return yields identical results, only
subtracting 1 from each data point.)
We first looked at possible
distributions. Figure 7.1 shows the Crystal Ball best fit for all data
(using the Chi-square criterion—same result for Kolmogorov-Smirnov
or Anderson criteria), while Fig. 7.2 shows fit with the
logistic distribution, and Fig. 7.3 with the normal distribution:
Fig.
7.1
Data distribution fit student-t. ©Oracle.
used with permission
Fig.
7.2
Logistic fit. ©Oracle. used with
permission
Fig.
7.3
Normal model fit to data. ©Oracle. used
with permission
The parameters for the student-t
distribution fit was a scale of 0.01, and 2.841 degrees of freedom.
For the logistic distribution, the scale parameter was 0.01.
The data had a slight negative skew,
with a skewness score of −1.87. It had a high degree of kurtosis
(73.65), and thus much more peaked than a normal distribution. This
demonstrates “fat tail” distributions that are often associated
with financial returns. Figures 7.1, 7.2, 7.3 clearly show how the normal assumption is
too spread out for probabilities close to 0.5, and too narrow for
the extremes (tails). The logistic distribution gives a better fit,
but student-t distribution does better yet.
Table 7.5 shows means standard
deviations, and covariances of these investments.
Table
7.5
Daily data
Ford
|
IBM
|
Pfizer
|
SAP
|
WalMart
|
XOM
|
S&P
|
|
---|---|---|---|---|---|---|---|
Mean
|
1.00084
|
1.00033
|
0.99935
|
0.99993
|
1.00021
|
1.00012
|
0.99952
|
Std. Dev
|
0.03246
|
0.02257
|
0.02326
|
0.03137
|
0.02102
|
0.02034
|
0.01391
|
Min
|
0.62822
|
0.49101
|
0.34294
|
0.81797
|
0.53203
|
0.51134
|
0.90965
|
Max
|
1.29518
|
1.13160
|
1.10172
|
1.33720
|
1.11073
|
1.17191
|
1.11580
|
Cov(Ford)
|
0.00105
|
0.00019
|
0.00014
|
0.00020
|
0.00016
|
0.00015
|
0.00022
|
Cov(IBM)
|
0.00051
|
0.00009
|
0.00016
|
0.00013
|
0.00012
|
0.00018
|
|
Cov(Pfizer)
|
0.00054
|
0.00011
|
0.00014
|
0.00014
|
0.00014
|
||
Cov(SAP)
|
0.00098
|
0.00010
|
0.00016
|
0.00016
|
|||
Cov(WM)
|
0.00044
|
0.00011
|
0.00014
|
||||
Cov(XOM)
|
0.00041
|
0.00015
|
|||||
Cov(S&P)
|
0.00019
|
An alternative statistic for returns
is the logarithmic return, or continuously compounded return, using
the formula:
The student’s t distribution again had
the best fit, followed by logistic and normal (see Fig.
7.4):
Fig.
7.4
Distribution comparison from Crystal Ball.
©Oracle. used with permission
This data yields slightly different
data, as shown in Table 7.6.
Table
7.6
Daily data for logarithmic return
Ford
|
IBM
|
Pfizer
|
SAP
|
WalMart
|
XOM
|
S&P
|
|
---|---|---|---|---|---|---|---|
Mean
|
−0.00029
|
0.00015
|
−0.00084
|
−0.00038
|
0.00006
|
−0.00017
|
−0.00068
|
Std. Dev
|
0.03278
|
0.02455
|
0.02852
|
0.03087
|
0.02254
|
0.02219
|
0.01392
|
Min
|
−0.46486
|
−0.71130
|
−1.07021
|
−0.20093
|
−0.63105
|
−0.67073
|
−0.09470
|
Max
|
0.25865
|
0.12364
|
0.09687
|
0.29058
|
0.10502
|
0.15863
|
0.10957
|
Cov(Ford)
|
0.00107
|
0.00019
|
0.00013
|
0.00020
|
0.00016
|
0.00015
|
0.00022
|
Cov(IBM)
|
0.00060
|
0.00009
|
0.00015
|
0.00013
|
0.00012
|
0.00018
|
|
Cov(Pfizer)
|
0.00081
|
0.00011
|
0.00014
|
0.00013
|
0.00014
|
||
Cov(SAP)
|
0.00095
|
0.00010
|
0.00016
|
0.00016
|
|||
Cov(WM)
|
0.00051
|
0.00011
|
0.00014
|
||||
Cov(XOM)
|
0.00049
|
0.00015
|
|||||
Cov(S&P)
|
0.00019
|
Like the arithmetic return, the
logarithmic return is centered on 0. There is a difference (slight)
between logarithmic return covariances and arithmetic return
covariances. The best distribution fit was obtained with the
original data (identical to arithmetic return), so we used that
data for our chance constrained calculations. If logarithmic return
data was preferred, the data in Table 7.6 could be used in the
chance constrained formulations.
Chance Constrained Model Results
We ran the data into chance
constrained models assuming a normal distribution for data, using
means, variances, and covariances from Table 7.5. The model included a
budget limit of $1000, all variables ≥0, (chance constrained to
have no loss), obtaining results shown in Table 7.7.
Table
7.7
Model results
Model
|
Ford
|
IBM
|
Pfizer
|
SAP
|
WM
|
XOM
|
S&P
|
Return
|
Stdev
|
---|---|---|---|---|---|---|---|---|---|
Max return
|
1000.000
|
–
|
–
|
–
|
–
|
–
|
–
|
1000.84
|
32.404
|
Min variance
|
–
|
45.987
|
90.869
|
30.811
|
127.508
|
116.004
|
588.821
|
999.76
|
13.156
|
Normal
Pr{>970}>0.95
|
398.381
|
283.785
|
–
|
–
|
222.557
|
95.277
|
–
|
1000.49
|
18.534
|
t Pr{>970}>0.95
|
607.162
|
296.818
|
–
|
–
|
96.020
|
–
|
–
|
1000.63
|
23.035
|
t Pr{>970}>0.95
Pr{>980}>0.9
|
581.627
|
301.528
|
–
|
–
|
116.845
|
–
|
–
|
1000.61
|
22.475
|
t Pr{>970}>0.95
Pr{>980}>0.9
Pr{>990}>0.8
|
438.405
|
279.287
|
–
|
–
|
220.254
|
62.054
|
–
|
1000.51
|
19.320
|
Max Pr{>1000}
|
16.275
|
109.867
|
105.586
|
38.748
|
174.570
|
172.244
|
382.711
|
999.91
|
13.310
|
Maximizing return is a linear
programming model, with an obvious solution of investing all
available funds in the option with the greatest return (Ford). This
has the greatest expected return, but also the highest
variance.
Minimizing variance is equivalent to
chance constrained form (2). The solution avoided Ford (which had a
high variance), and spread the investment out among the other
options, but had a small loss.
A series of models using chance
constrained form (1) were run. Maximizing expected return subject
to investment ≤1000 as well as adding the chance constraint
Pr{return ≥ 970} was run for both normal and
t-distributions.
It can be seen in Table 7.6 that the
t-distribution was less restrictive, resulting in more investment
in the riskier Ford option, but having a slightly higher variance
(standard deviation). The chance constraint was binding in both
assumptions (normal and Student-t). There was a 0.9 probability
return of 979.50, and a 0.8 probability of return of 988.09 by
t-distribution. Further chance constraint models were run assuming
t-distribution. For the model:
The expected return was only slightly
less, with the constraint
Pr{return ≥ 980} ≥ 0.9 binding. There was a
0.95 probability of return of 970.73, and a 0.8 probability of
return of 988.38. A model using three chance constraints was also
run:
This yielded a solution where the 0.95
probability of return was 974.83, the 0.9 probability of return was
982.80, and the 0.8 probability of return was 990 (binding).
Finally, a model was run to maximizing
probability of return ≥1000 (chance constrained model type 3).
This was done by setting the deviation
from an infeasible target. The solution yielded a negative expected
return at a low variance, with the 0.95 probability of return
982.22, the 0.9 probability of return 987.71, and the 0.8
probability of return 992.67.
Conclusions
A number of different types of models
can be built using chance constraints. The first form is to
maximize the linear expected return subject to attaining specified
probabilities of reaching specified targets. The second is to
minimize variance. This second form is not that useful, in that the
lowest variance is actually to not invest. Here we forced
investment of the 1000 capital assumed. The third form is to
maximize probability of attaining some target, which in order to be
useful, has to be infeasible.
Chance constrained models have been
used in many applications. Here we have focused on financial
planning, but there have been applications whenever statistical
data is available in an optimization problem.
The models presented all were solved
with EXCEL SOLVER. In full disclosure, we need to point out that
chance constraints create nonlinear optimization models, which are
somewhat unstable relative to linear programming models. Solutions
are very sensitive to the accuracy of input data. There also are
practical limits to model size. The variance-covariance matrix
involves a number of parameters to enter into EXCEL functions,
which grow rapidly with the number of variables. In the simple
example there were three solution variables, with six elements to
the variance-covariance matrix. In the real example, there were
seven solution variables (investment options). The
variance-covariance matrix thus involved 28 nonlinear
expressions.
Notes
- 1.
Charnes, A. and Cooper, W.W. (1959). Chance-constrained programming, Management Science 6:1, 73–79; Charnes, A. and Cooper, W.W. (1962). Chance-constraints and normal deviates, Journal of the American Statistical Association 57, 134–148.
- 2.
Charnes, A. and Cooper, W.W. (1963). Deterministic equivalents for optimizing and satisficing under chance-constraints, Operations Research 11:1, 18–39.
- 3.
Goicoechea, A. and Duckstein, L. (1987). Nonnormal deterministic equivalents and a transformation in stochastic mathematical programming, Applied Mathematics and Computation 21:1, 51–72.
- 4.
Booth, L. (2004). Formulating retirement targets and the impact of time horizon on asset allocation, Financial Services Review 13:1, 1–17.
- 5.
Dupaĉová, J. and Polivka, J. (2007). Stress testing for VaR and CVaR. Quantitative Finance 7(4), 411–421.
- 6.
Bilsel, R.U. and Ravindran, A. (2011). A multiobjective chance constrained programming model for supplier selection under uncertainty. Transportation Research: Part B 45(8), 1284–1300.
- 7.
Wibowo, A. and Kochendoerfer, B. (2011). Selecting BOT/PPP infrastructure projects for government guarantee portfolio under conditions of budget and risk in the Indonesian context. Journal of Construction Engineering & Management 137(7), 512–522.
- 8.
Gurgur, C.Z. and Morley, C.T. (2008). Lockheed Martin Space Systems Company optimizes infrastructure project-portfolio, Interfaces 38:4, 251–262.
- 9.
Held, H., Kriegler, E., Lessmann, K. and Edenhofer, O. (2009). Efficient climate policies under technology and climate uncertainty, Energy Economics 31, S50–S61.
- 10.
Cooper, W.W., Deng, H., Huang, Z. and Li, S.X. (2002). Chance constrained programming approaches to technical efficiencies and inefficiencies in stochastic data envelopment analysis, Journal of the Operational Research Society 53:12, 1347–1356; Cooper, W.W., Deng, H., Huang, Z. and Li, S.X. (2004). Chance constrained programming approaches to congestion in stochastic data envelopment analysis, European Journal of Operational Research 155:2, 487–501.
- 11.
Wu, D. and Olson, D.L. (2008). Supply chain risk, simulation, and vendor selection, International Journal of Production Economics 114:2, 646–655.
- 12.
Lee, S.M. and Olson, D.L. (2006). Introduction to Management Science 3rd ed. Cincinnati: Thompson.