Chance-Constrained Approaches for Multiobjective Stochastic Linear Programming Problems ()
1. Introduction
Decision makers are intendedly rational. They are goal directed and they are intended to pursue those goals in conformity with the classic homo-economicus model [1]. They do not always succeed because of the complexity of some environments that impose both procedural and substantive limits. This is the case when dealing with multiobjective stochastic linear programming (MSLP) problems.
In such a turbulent environment the notion of “optimum optimorum” is not clearly defined and satisficing rather than optimal search behavior seems to be the most appropriate option. A look at the literature reveals that most existing solution concepts for MSLP problems rely heavily on the expected, pessimistic and optimistic values of involved random variables [2,3]. A finding from several research work [4-7] leave no doubt about the fact that these values may be useful in providing the range of possible outcomes. Nevertheless, they ignore such important factors as the size and the probability of deviations outside the likely range as well as other aspects concerning the dispersion of the probabilities.
In this paper, we discuss satisfying solution concepts for MSLP problems. These concepts are based on the chance-constrained philosophy [8]. Chance-constrained applied for the purpose of limiting the probability that constraint will be violated. In this form, it adds considerably to both the flexibility and reality of the stochastic model under consideration. Mathematical characterization of the above mentioned solution concepts are also provided along with ways for singling them out. A numerical example is supplemented for the sake of illustration.
The remainder of the paper is organized as follows. In the next section we clearly formulate the problem under consideration. In Section 3, we present some satisfying solution concepts for this problem. In Section 4, we characterize these solution concepts. In Section 5, we discuss ways for solving resulting problems. In Section 6, we present the methods for solving this problem. An illustrative example is given in Section 7. We end up with some concluding remarks along with lines for further developments in the field of MSLP.
2. Multiobjective Stochastic Linear Programming
Problem Formulation
A multiobjective stochastic linear programming is a problem of the following type:
where 
are random vectors defined on a probability space
,
where 
are random variables defined on the same probability space.
(P1) is an ill-defined problem because of the simultaneous presence of different objective functions and of randomness surrounding data. In such a turbulent environment, neither the notion of feasibility nor that of optimality is clearly defined. One then has to resort to the Simon’s bounded rationality principle [9] and seek for a satisfying solution instead of an optimal one.
Several solution concepts have been described in the literature, see for instance [10,11]. Most of these solution concepts rely on the first two moments of involved random variables. As mentioned earlier, these values often offer a short-sighted view of uncertainty surrounding data under consideration. In what follows, we discuss some satisfying solution concepts based on the chanceconstrained approach [12-14].
3. Satisfying Solutions for Problem (P1)
Definition 3.1 
-satisfying solution of type 1 Assume that objective functions of (P1) are aggregated in the form of
. We say that 
is an 
-satisfying solution of type 1 for 
if 
is optimal for the following optimization problem:
where 
with 
and 
and β are probability levels a priori fixed by the Decision Maker.
Definition 3.2 
-satisfying solution of type 2 We say that 
is an 
-satisfying solution of type 2 for (P1) if
, where
, is efficient for the following multiobjective optimization problem:
Here 
and 
are threshold fixed by the Decision Maker.
Definition 3.3 
-satisfying solution of type 3 We say that 
is an 
-satisfying solution of type 3 for (P1) if
, where
, is optimal for the following mathematical program:
Here
, 
and 
are respectively the upper deviations of the 
goal, the weight of 
and the target associated with the 
objective function. 
and 
are as in Definition 3.2.
Interpretation
Intuitive ways of thinking about the above solution concepts are given below.
• An 
-satisfying solution of type 1 for 
is an alternative that keeps the probability of the aggregate 
of the objective functions 
of this problem, lower than a variable s to a desired extend β, while the variable s is itself minimized. Moreover the chance of meeting the 
constraint of the problem is requested to be higher than fixed thresholds
. It is clear that for 
and β close to 1, such an alternative is an interesting one. As a matter of fact, it maintains the probability of keeping the aggregation of objective functions low, while keeping the probabilities of realization of constraints to desired extents.
• An 
-satisfying solution of type 2 for 
is an action that keeps the probability of the 
objective 
of the problem be less than some variable
to a level
: while the vector 
is minimized in the Pareto sense. In the meantime, the chance of having the 
constraint of the problem be satisfied is greater than
. Again for
, 
and
, 
close to 1, such a solution is interesting from the stand points of feasibility and efficiency.
• Finally, an 
-satisfying solution of type 3 for 
minimizes the weighted sum of derivations from given targets while maintaining the probability of each objective to be close to the corresponding target, to some desired levels. It also meets the requirement of being feasible with high probability.
4. Characterization of Satisfying Solutions
In what follows, we provide necessary and sufficient conditions for a potential action to be a satisfying one, in the above described sense. These conditions rely heavily on the hypothesis of normality of distributions of involved random variables.
We recall that random vector 
is said to have the multivariate normal distribution if any linear combination of its components is normally distributed. The following Lemma due to Kataoka [13] will be needed in the sequel.
Lemma 4.1
1) Assume that 
are independent and normally distributed random variables with mean
respectively.
Then for
, 
the aggregation 
is normally distributed with mean
and variance 
2) Suppose 
has a multivariate normal distribution with mean
and let 
be the covariance of 
and 
Then for any
, the inner product 
is normally distributed with mean
and variance
.
We are now in position to characterize an 
- satisfying solution of type 1.
Proposition 4.1
Assume that objective functions of (P1) is aggregated as follows 
where,
, 
Suppose that the random variables,
; 
are independent and normally distributed. Suppose also that for any
, the random variables 
and 
are normally distributed and independent. Then a point 
is an 
-satisfying solution of type 1 for (P1) if and only if 
is optimal for the problem:
where
, 
, 
denotes the 
row of the matrix 
and
Proof
Assume that 
is a satisfying solution of type 1 for (P1), then 
is a solution of
Let’s show that the first constraint of (P2) is equivalent to
(1)
Indeed we have by Lemma 4.1 that 
is normally distributed with mean 
and variance 
.
Then
because
is normally distributed with mean 0 and variance 1. Therefore the first constraint of 
becomes
That is
which equivalent is to:
And we have established that the first constraint of
is equivalent to relation (1).
Define now the random variables
are independent and normally distributed [15].
The expected value of 
is
(2)
and its variances is
. (3)
The chance constraints
(4)
can therefore, be written as
; 
which can also be expressed as
or 
where
Thus the chance constraints (4) can be merely written:
that is
which leads to 
replacing 
and 
by their values given by (2) and (3) respectively in (4), we obtain
(5)
combining relations (1) and (5) we obtain that 
is optimal to the following program:
This problem is equivalent to (P2)' as desired.
As far as 
-satisfying solution of type 2 is concerned we have the following result.
Proposition 4.2
Consider (P1) and assume that the random variables 
; 
are independent and normally distributed. Assume further that the random variables
;
; 
and
; 
are also normally distributed and independent. Then a point 
is an 
-satisfying solution of type 2 for (P1) if and only if 
is efficient for the following mathematical program:
where
; 
and 
denotes the 
row of the matrix 
and
.
Proof
As shown in the proof of Proposition 4.1, the chance constraints 
in (P3) are equivalent to
and the chance constraints:
are equivalent to
Then (P3) is equivalent to the following program:
And clearly, this problem is equivalent to (P3)' in the sense that they have the same efficient solutions. Finally, a characterization of an 
-satisfying solution of type 3 is given below.
Proposition 4.3
Consider (P1) and assume that the random variables
,
; 
are independent and normally distributed. Then a point 
is an 
-satisfying solution of type 3 for problem (P1) if and only if 
is optimal for the following mathematical program:
where 
is the upper deviation variable of the 
goal, 
are weights of the upper deviation variables, 
are targets associated with the objective functions; 
denotes the 
row of the matrix 
and
, 
are desired thresholds fixed by the Decision Maker.
Proof.
Consider
As discussed in the proof of Proposition 4.2, the chance constraints
are equivalent to
As shown in the proof of Proposition 4.1, we have that
can be written as follow:
Therefore, program 
reads:
which is exactly (P4)'.
5. Singling out Satisfying Solution for Problem (P1)
Problem to be solved to single out a satisfying solution (in the sense of definitions given in, §2 for (P1) are (P2)', (P3)' and (P4)' depending on the type of solution chosen. (P2)' and (P4)' are standard mathematical programs about which a great deal is known. In the case, when these programs are convex, one may use algorithms of convex programming [16], the conjugate gradient method [17], the exterior or interior penalty functions methods [18]. For the non convex case, one may use approximation type algorithms or metaheuristics [19]. (P3)' is a multiobjective program. A rich array of methods for solving it may be found in [20].
6. Methods for Solving (P1)
6.1. Method for Yielding a Satisfying Solution of Type 1
Step 1: Fix 
and
; 
;
Step 2: Compute
;
;
Step 3: Compute
;
Step 4: Agregate 
to
;
Step 5: Compute
, 
, 
,
;
Step 6: Write the Program
;
Step 7: Solve 
using a mathematical programming method. Let 
is solution;
Step 8: Print: “
is a satisfying solution of type1 for (P1)”;
Step 9: Stop.
6.2. Method for Yielding a Satisfying Solution of Type 2
The same as 6.1; except that in Step 1 
should be replaced by 
In Step 4, 
should be replaced by 
and
, 
respectively.
Steps 5-7 should be as follow:
Step 5: Write the Program
;
Step 6: “Solve
” and in;
Step 7, “
is a satisfying solution of type 2”;
Step 8: Stop.
6.3. Method for Yielding a Satisfying Solution of Type 3
Step 1: Fix 
and
;
Step 2: Fix
, 
and
,
;
Step 3: Compute:
, 
, 
,
;
Step 4: Compute:
,
; 
, 
, 
, 
,
;
Step 5: Write
;
Step 6: Solve 
let 
its solution;
Step 7: Print: “
is a satisfying solution of type 3”;
Step 8: Stop.
7. Numerical Example
Consider the following multiobjective stochastic linear program:
where
, 
are independent normally distributed random variables, with the following parameters:
if the decision maker is interested in a satisfying solution of type 1 with 
and 
and 
then by virtue of Proposition 4.1, he has to solve the following problem.
solving this optimization problem using MATLAB, we obtain the following solution:
.
Assume now that a satisfying solution of type 2 is sought with 
and 
.
Then by Proposition 4.2, one has to solve the following problem:
using the global criterion method [21] and solving the resulting problem by MATLAB, we obtain the following solution:
Suppose that a satisfying solution of type 3 is desirable for
and 
. Suppose further that the decision maker goals are 2,000 and 15,000 for objectives 1 and 2 respectively. Using equal weights (i.e. 
for the two objectives, we have to solve the following problem:
using MATLAB to solve this problem, we obtain the following solution:
, 
, 
, with optimal value 
.
As can be seen, methods yielding type 2 and type 3 satisfying solutions have almost the same solution that differs from the method yielding type 1 solution satisfying solution. This is because the two first methods use the multiobjective approach while the third method uses the stochastic approach.
8. Concluding Remarks
In this paper, we have addressed the problems of defining and characterizing solution concepts for a multiobjective stochastic linear program. Owing to the simultaneous presence of randomness and to the multiplicity of objective functions, we have privileged the satisfying approach rather than the optimizing one.
Solution concepts discussed in this paper have an advantage over those focusing only on the expectation and variances. As a matter of fact, these solutions take into consideration, the whole distributions of involved random variables. We have shown that when involved random variables are normally distributed, singling out solutions discussed here causes little extra computational costs. As a matter of fact, problems to be solved to obtain such solutions are standard mathematical programs about which a great deal is known. Lines for further developments in this field include:
• The choice of threshold
, 
, and
, 
in an optimal way;
• The consideration of other distributions rather than the normal one;
• The extension of solution concepts discussed here to the case where fuzziness and randomness are in the state of affairs [22];
• The generalization of methods discussed here to the bilevel case [23].