Birge J.R., Louveaux F. Introduction to Stochastic Programming
Подождите немного. Документ загружается.
164 4 The Value of Information and the Stochastic Solution
s. t. Ax = b,x ≥0 , (1.1)
as the optimization problem associated with one particular scenario
ξ
,where,as
before,
ξ
(
ω
)
T
=(q(
ω
)
T
,h(
ω
)
T
,T
1·
(
ω
),...,T
m
2
·
(
ω
)) . To make the definition com-
plete, we repeat the notation, K
1
= {x | Ax = b , x ≥ 0} and K
2
(
ξ
)={x |∃y ≥
0s.t. Wy = h −Tx} .Wedefine z(x,
ξ
)=+∞ if x ∈ K
1
∩K
2
(
ξ
) and z(x,
ξ
)=−∞
if (1.1) is unbounded below. We again use the convention +∞+(−∞)=+∞ .
We may also reasonably assume that for all
ξ
∈
Ξ
, there exists at least one
x ∈ ℜ
n
1
such that z(x,
ξ
) < ∞ . (Otherwise, there would exist one scenario for
which no feasible solution exists at all. No reasonable stochastic model could be
constructed in such a situation.) This assumption implies that, for all
ξ
∈
Ξ
,there
exists at least one feasible solution, which in turn implies the existence of at least
one optimal solution. Let ¯x(
ξ
) denote some optimal solution to (1.1). As in a sce-
nario approach, we might be interested in finding all solutions ¯x(
ξ
) of problem
(1.1) for all scenarios and the related optimal objective values z( ¯x(
ξ
),
ξ
) .
This search is known as the distribution problem (as we mentioned in Sec-
tion 3.1c.) because it looks for the distribution of ¯x(
ξ
) and of z( ¯x(
ξ
),
ξ
) in terms of
ξ
. The distribution problem can be seen as a generalization of sensitivity analysis
or parametric analysis in linear programming.
Here, we assume we somehow have the ability to find these decisions ¯x(
ξ
) and
their objective values z( ¯x(
ξ
),
ξ
) so that we are in a position to compute the expected
value of the optimal solution, known in the literature as the wait-and-see solution
(WS, see Madansky [1960]) where
WS= E
ξ
min
x
z(x,ξ)
= E
ξ
z( ¯x(ξ),ξ) . (1.2)
We may now compare the wait-and-see solution to the so-called here-and-now so-
lution corresponding to the recourse problem (RP) defined earlier in Chapter 3 as
(1.1), and we may now write that as
RP = min
x
E
ξ
z(x,ξ) , (1.3)
with an optimal solution, x
∗
.
The expected value of perfect information is, by definition, the difference be-
tween the wait-and-see and the here-and-now solution, namely,
EVPI = RP−WS . (1.4)
An example was given in Chapter 1 in the farmer’s problem. The wait-and-see solu-
tion value was −$115,406 (when converted to a minimization problem), while the
recourse solution value was −$108,390 . The expected value of perfect information
for the farmer was then $7016.
4.2 The Value of the Stochastic Solution 165
This is how much the farmer would be ready to pay each year to obtain perfect
information on next summer’s weather. A meteorologist could reasonably ask him
to pay part of this amount to support meteorological research.
4.2 The Value of the Stochastic Solution
For practical purposes, many people would believe that finding the wait-and-see
solution or equivalently solving the distribution problem is still too much work (or
impossible if perfect information is just not available at any price). This is especially
difficult because the wait-and-see approach delivers a set of solutions instead of one
solution that would be implementable.
A natural temptation is to solve a much simpler problem: the one obtained by
replacing all random variables by their expected values. This is called the expected
value problem or mean value problem, which is simply
EV = min
x
z(x,
¯
ξ
) , (2.1)
where
¯
ξ
= E(ξ) denotes the expectation of ξ . Let us denote by ¯x(
¯
ξ
) an optimal
solution to (2.1), called the expected value solution. Anyone aware of some stochas-
tic programming or realizing that uncertainty is a fact of life would feel at least a
little insecure about advising to take decision ¯x(
¯
ξ
) . Indeed, unless ¯x(
ξ
) is some-
how independent of ξ , there is no reason to believe that ¯x(
¯
ξ
) is in any way near
the solution of the recourse problem (1.3).
The value of the stochastic solution (first introduced in Chapter 1) is the concept
that precisely measures how good or, more frequently, how bad a decision ¯x(
¯
ξ
) is
in terms of (1.3). We first define the expected result of using the EV solution to be
EEV = E
ξ
(z(¯x(
¯
ξ
),ξ)) . (2.2)
The quantity, EEV , measures how ¯x(
¯
ξ
) performs, allowing second-stage deci-
sions to be chosen optimally as functions of ¯x(
¯
ξ
) and
ξ
. The value of the stochas-
tic solution is then defined as
VSS = EEV −RP . (2.3)
Recall, for example, that in Section 1.1 this value was found using EEV = −
$107,240 and RP = −$108,390 , for VSS = $1150 . This quantity is the cost of
ignoring uncertainty in choosing a decision.
166 4 The Value of Information and the Stochastic Solution
4.3 Basic Inequalities
The following relations between the defined values have been established by Madan-
sky [1960]. Generalizations to nonlinear functions can be found in Mangasarian and
Rosen [1964].
Proposition 1.
WS≤ RP ≤EEV . (3.1)
Proof: For every realization,
ξ
, we have the relation
z( ¯x(
ξ
),
ξ
) ≤z(x
∗
,
ξ
) ,
where, as said before, x
∗
denotes an optimal solution to the recourse problem (1.3).
Taking the expectation of both sides yields the first inequality. x
∗
being an optimal
solution to the recourse problem (1.3) while ¯x(
¯
ξ
) is just one solution to (1.3) yields
the second inequality.
Proposition 2. For stochastic programs with fixed objective coefficientsand fixed
W,
EV ≤WS . (3.2)
Proof: First, note that z(x,
ξ
=(h, T)) = c
T
x + Q(x,h,T )+
δ
(x|Ax = b,x >= 0) ,
where
δ
(x|X) is the indicator function of the point x for set X , is jointly convex
in x , h ,and T .Now,toshowthat f (
ξ
)=min
x
z(x,
ξ
) is convex in
ξ
, consider
ξ
1
and
ξ
2
where z (x
1
,
ξ
1
)= f (
ξ
1
) and z(x
2
,
ξ
2
)= f (
ξ
2
) ,then
λ
f (
ξ
1
)+(1 −
λ
) f (
ξ
2
)=
λ
z(x
1
,
ξ
1
)+(1 −
λ
)z(x
2
,
ξ
2
)
≥ z(
λ
(x
1
,
ξ
1
)+(1 −
λ
)(x
2
,
ξ
2
)
≥ min
x
z(x,
λξ
1
+(1 −
λ
)
ξ
2
)
= f (
λξ
1
+(1 −
λ
)
ξ
2
),
establishing convexity of f (
ξ
) . Now, Jensen’s inequality (Jensen [1906]) states that
for any convex function f (ξ) of ξ ,Ef (ξ) ≥ f (Eξ) .
Proposition 2 does not hold for general stochastic programs. Indeed, if we con-
sider q only to be stochastic, by Theorem 3.5 the function z(x,
ξ
) is a concave
function of
ξ
and Jensen’s inequality does not apply. An example of a program
where EV > WS is given in Exercise 3.
Other bounds can be obtained. We give two more examples of such bounds here.
Proposition 3. Let x
∗
represent an optimal solution to the recourse problem (1.3)
and let ¯x(
¯
ξ
) be a solution to the expected value problem (1.4).Then
RP ≥ EEV +(x
∗
− ¯x(
¯
ξ
))
T
η
, (3.3)
4.4 The Relationship between EVPI and VSS 167
where
η
∈
∂
E
ξ
z( ¯x(
¯
ξ
),ξ) , the subdifferential set of E
ξ
z(x,ξ) at ¯x(
¯
ξ
) .
Proof: By convexity of E
ξ
z(x,ξ) , the subgradient inequality applied at point x
1
implies that for any x
2
the relation E
ξ
z(x
2
,ξ) ≥ E
ξ
z(x
1
,ξ)+(x
2
−x
1
)
T
η
holds.
The proposition follows by application of this relation for x
1
= ¯x(
¯
ξ
) and x
2
= x
∗
,
by noting that RP = E
ξ
z(x
∗
,ξ) and EEV = E
ξ
z( ¯x(
¯
ξ
),ξ ).
The last bound is obtained by considering a slightly different version of the re-
course problem, defined as follows:
minz
u
(x,ξ)=c
T
x + min{q
T
y |Wy ≥h(ξ) −Tx, y ≥ 0}
s. t. Ax = b ,
x ≥0 .
(3.4)
Problem (3.4) differs from problem (1.1) because in (3.4) only the right-hand side
is stochastic and the second-stage constraints are inequalities. It is not difficult to
observe that all definitions and relations also apply to z
u
. If we further assume that
h(ξ) is bounded above, then an additional inequality results.
Proposition 4. Consider problem (3.4) and the related definition
RP = min
x
E
ξ
z
u
(x,ξ) .
Assume further that h(ξ) is bounded above by a fixed quantity h
max
.Let x
max
be
an optimal solution to z
u
(x,h
max
) .Then
RP ≤ z
u
(x
max
,h
max
) . (3.5)
Proof:Forany
ξ
in
Ξ
and any x ∈ K
1
, a feasible solution to Wy ≥ h
max
−
Tx, y ≥0, is also a feasible solution to Wy≥h(
ξ
)−Tx, y ≥0.Hence z
u
(x,h
max
) ≥
z
u
(x,h(
ξ
)) . Thus z
u
(x,h
max
) ≥E
ξ
z
u
(x,h(ξ)) , hence z
u
(x,h
max
)
≥min
x
E
ξ
z
u
(x,h(ξ)) = RP .
4.4 The Relationship between EVPI and VSS
The quantities, EVPI and VSS , are often different, as our examples have shown.
This section describes the relationships that exist between the two measures of un-
certainty effects.
From the inequalities in the previous section, the following proposition holds.
Proposition 5.
a. For any stochastic program,
0 ≤ EVPI , (4.1)
168 4 The Value of Information and the Stochastic Solution
0 ≤ VSS . (4.2)
b. For stochastic programs with fixed recourse matrix and fixed objective coeffi-
cients,
EVPI ≤ EEV −EV , (4.3)
VSS ≤ EEV −EV . (4.4)
The proposition indicates that the EVPI and the VSS are (both) nonnegative (any-
one would be surprised if this was not true) and are both bounded above by the same
quantity EEV −EV , which is easily computable. It follows that when EV = EEV ,
both the EVPI and VSS vanish. A sufficient condition for this to happen is to have
¯x(ξ) independent of ξ . This means that optimal solutions are insensitive to the
value of the random elements. In such situations, finding the optimal solution for
one particular
ξ
(or for
¯
ξ
) would yield the same result, and it is unnecessary to
solve a recourse problem. Such extreme situations rarely occur.
From these observations, three lines of research have been addressed. The first
one studies relationships between EVPI and VSS . It is illustrated in the sequel of
this paragraph by showing an example where EVPI is zero and VSS is not and
an example of the reverse. The second one studies classes of problems for which
one can observe or theorize that the EVPI is low. Examples and counterexamples
are given in Section 4.5. The third one studies refined bounds on EVPI and VSS .
Results about refined upper and lower bounds on EVPI and VSS appear in Sec-
tion 4.6.
We thus end this section by showing examples taken from Birge [1982] that
illustrate cases in which one of the two concepts ( EVPI and VSS ) is null and the
other is positive.
a. EVPI = 0 and VSS = 0
Consider the following problem
z(x,ξ)=x
1
+ 4x
2
+ min{y
1
+ 10y
+
2
+ 10y
−
2
|
y
1
+ y
+
2
−y
−
2
= ξ + x
1
−2x
2
,y
1
≤ 2,y ≥0}
s. t. x
1
+ x
2
= 1 ,
x ≥ 0 ,
(4.5)
where the random variable ξ follows a uniform density over [1,3] .Foragiven x
and
ξ
, we may conclude that
4.4 The Relationship between EVPI and VSS 169
y
∗
(x,
ξ
)=
⎧
⎪
⎨
⎪
⎩
y
1
=
ξ
+ x
1
−2x
2
, y
2
= 0if0≤
ξ
+ x
1
−2x
2
≤ 2 ,
y
1
= 2 , y
+
2
=
ξ
+ x
1
−2x
2
−2if
ξ
+ x
1
−2x
2
> 2 ,
y
−
2
= 2x
2
−
ξ
−x
1
if
ξ
+ x
1
−2x
2
< 0 ,
so that
z(x,
ξ
)=
⎧
⎪
⎨
⎪
⎩
2x
1
+ 2x
2
+
ξ
if 0 ≤
ξ
+ x
1
−2x
2
≤ 2 ,
−18 + 11x
1
−16x
2
+ 10
ξ
if
ξ
+ x
1
−2x
2
> 2 ,
−9x
1
+ 24x
2
−10
ξ
if
ξ
+ x
1
−2x
2
< 0 .
Given the first-stage constraint x
1
+ x
2
= 1 , one has z(x,
ξ
)=2 +
ξ
in the first
of these three regions. Now, using the first-stage constraint and the definition of
the regions, one can easily check that z(x,
ξ
) ≥ 2 +
ξ
in the other two regions.
Hence, any ˆx ∈{(x
1
,x
2
) | x
1
+ x
2
= 1 , x ≥ 0} is an optimal solution of (4.5)for
−x
1
+ 2x
2
≤
ξ
≤ 2 −x
1
+ 2x
2
, or equivalently for 2 −3x
1
≤
ξ
≤ 4 −3x
1
.
In particular,
1
3
,
2
3
is optimal for all
ξ
, (0,1) is optimal for all
ξ
∈ [2,3] ,
and (1,0) is optimal for
ξ
= {1}.
Taking ¯x(
ξ
)=
1
3
,
2
3
for all
ξ
leads to the conclusion that ¯x(
ξ
) is identical
for all
ξ
, hence WS = RP = 4, so that EVPI = 0 . On the other hand, solving
z(x,
¯
ξ
= 2) may yield a different solution, for example, ¯x(2)=(0,1) , with EV = 4.
In that case,
EEV = E
ξ≤2
(24 −10
ξ
)+E
ξ≥2
(2 +
ξ
)=
27
4
,
so that VSS = 11/4.
Because linear programs often include multiple optimal solutions, this type of
situation is far from exceptional.
b. VSS = 0 and EVPI = 0
We consider the same function z(x,
ξ
) with
ξ
∈
0,
3
2
,3
, with each event occur-
ring with probability 1/3.
For
ξ
= 0, ¯x(0)=
x | x
1
+ x
2
= 1,
2
3
≤ x
1
≤ 1
.
For
ξ
= 3/2, ¯x(3/2)={x | x
1
+ x
2
= 1,1/6 ≤ x
1
≤ 5/6}.
For
ξ
= 3, ¯x(3)={x | x
1
+ x
2
= 1,0 ≤x
1
≤ 1/3}.
Let us take ¯x(3/2)=(2/3,1/3) .Then EV = z( ¯x,3/2)=2 + 3/ 2 = 7/2,and
EEV = 2 +
1
3
0 +
3
2
+ 12
= 2 +
13
2
= 13/2.
No single decision is optimal for the three cases, so we expect EVPI to be
nonzero. In the wait-and-see solution, it is possible for all three cases to take
a different optimal solution, such as ¯x(0)=(1,0) ,¯x(3/2)=(1/2,1/2) ,and
¯x(3)=(0,1) , yielding
170 4 The Value of Information and the Stochastic Solution
WS =
1
3
(1 + 1)+
1
3
5
2
+ 1
+
1
3
(4 + 1)
=
2
3
+
7
6
+
5
3
=
21
6
=
7
2
.
The recourse solution is obtained by solving the stochastic program
minE
ξ
(z(x,ξ)) , which yields x
∗
=(2/3,1/3) with the RP value equal to the EEV
value. Hence,
EV = WS = 7/2 ≤ RP = 13/2 = EEV ,
which means EVPI = 3 while VSS = 0.
4.5 Examples
There has always been a strong interest in trying to have a better understanding
of when the EVPI and VSS take large values and when they take low values. A
definite answer to this question would greatly simplify the practice of stochastic
programming. Only those programs with large EVPI or VSS would require the
solution of a stochastic program. Interested readers may find detailed examples in
the field of energy policy and exhaustible resources. Manne [1974] provides an ex-
ample where EVPI is low, while H.P. Chao [1981] elaborates general conditions
for EVPI to be low on a resource exhaustion model. By introducing other types of
uncertainty, Louveaux and Smeers [2011] and Birge [1988a] show related examples
where EVPI and/or VSS is large.
In this section, we provide simple examples to show that no general answer is
available. It is usually felt that using stochastic programming is more relevant when
there is more randomness in the problem. To translate this feeling into a more pre-
cise statement, we would, for example, expect that for a given problem, EVPI and
VSS would increase when the variances of the random variables increase. In the
following example, we show that this may or may not be the case.
Example 1
Let ξ be a single random variable taking the two values
ξ
1
and
ξ
2
, with probabil-
ity p
1
and p
2
, respectively, where p
2
= 1− p
1
.Let
¯
ξ
= E[ξ]=1/2.Let x be a
single decision variable. Consider the recourse problem:
min 6x+ 10E
ξ
|x −ξ|
s. t. x ≥ 0 .
4.6 Bounds on EVPI and VSS 171
(a) Let
ξ
1
= 1/3,
ξ
2
= 2/3, p
1
= p
2
= 1/2 serve as the reference setting.
We compute EVPI = 2/3andVSS = 1 . We also observe that the variance,
Var(ξ)=1/36 .
(b) Consider the case
ξ
1
= 0,
ξ
2
= 1 again with equal probability 1/2 (and un-
changed expectation). The variance Var(ξ) is now 1/4 , 9 times higher. We
now obtain EVPI = 2andVSS = 3 , showing an example where both values
clearly increase with the variance of ξ .
(c) Consider the case
ξ
1
= 0,
ξ
2
= 5/8 with probability p
1
= 0.2andp
2
=
0.8 , respectively. Again,
¯
ξ
= 0.5. Now, Var(ξ)=1/16 , larger than in (a).
We obtain EVPI = 2 , larger than in (a) but VSS = 0 . Knowing this result in
advance would mean that the solution of the deterministic problem with
¯
ξ
= Eξ
delivers the optimal solution (although EVPI is three times larger than in (a)).
(d) Consider the case
ξ
1
= 0.4,
ξ
2
= 0.8 with p
1
= 0.75 and p
2
= 0.25 , always
with
¯
ξ
= 0.5.Now, Var(ξ)=0.03 , slightly larger than in (a). We now observe
EVPI = 0.4andVSS = 1.1 , namely the opposite behavior from (c), a decrease
in EVPI and an increase in VSS.
(e) It is also felt that a more “difficult” stochastic program would induce higher
EVPI and VSS . One such case would be to have integer decision variables
instead of continuous ones. Exercise 3 of Section 1.1 shows that, with first-
stage integer variables for the farming problem, VSS remains almost unchanged
while EVPI even decreases. On the other hand, Exercise 4 of that section shows
that with second-stage integer variables, both EVPI and VSS strongly increase.
It would probably not be difficult to reach different conclusions by suitably
changing the data.
We may conclude from these simple examples that a general rule is unlikely to be
found. One alternative to such a rule is to consider bounds on the information and
solution value quantities that require less than complete solutions. We discuss these
bounds in the next section.
4.6 Bounds on EVPI and VSS
Bounds on EVPI and VSS rely on constructing intervals for the expected value
of solutions of linear programs representing WS , RP ,and EEV . The simplest
bounds stem from the inequalities in Proposition 5. The EVPI bound was suggested
in Avriel and Williams [1970] while the VSS form appears in Birge [1982]. Many
other bounds are possible with different limits on the defining quantities. In the
remainder of this section, we consider refined bounds that particularly address the
value of the stochastic solution. More general approaches to bound expectations of
value functions appear in Chapter 8.
The VSS bounds were developed in Birge [1982]. To find them, we consider
a simplified version of the stochastic program, where only the right-hand side is
stochastic (ξ = h(
ω
)) and
Ξ
is finite. Let
ξ
1
,
ξ
2
,...,
ξ
K
index the possible
172 4 The Value of Information and the Stochastic Solution
realizations of ξ ,and p
k
, k = 1,...,K be their probabilities. It is customary to
refer to each realization
ξ
k
of ξ as a scenario k .
To refine the bounds on VSS , we consider a reference scenario,say
ξ
r
.Two
classical reference scenarios are
¯
ξ
, the expected value of ξ , or the worst-case sce-
nario (for example, the one with the highest demand level for problems when costs
have to be minimized under the restriction that demand must be satisfied). Note that
in both situations the reference scenario may not correspond to any of the possible
scenarios in
Ξ
. This is obvious for
¯
ξ
. The worst-case scenario is, however, a pos-
sible scenario when, for example, ξ is formed by components that are independent
random variables. If the random variables are not independent, then a meaningful
worst-case scenario may be more difficult to construct. Let p
r
= P(ξ =
ξ
r
) be the
reference scenario’s probability.
The pairs subproblem of
ξ
r
and
ξ
k
is defined as
min z
P
(x,
ξ
r
,
ξ
k
)=c
T
x + p
r
q
T
y(
ξ
r
)+(1 − p
r
)q
T
y(
ξ
k
)
s. t. Ax = b ,
Wy(
ξ
r
)=
ξ
r
−Tx,
Wy(
ξ
k
)=
ξ
k
−Tx,
x,y ≥ 0 .
Let ( ¯x
k
, ¯y
k
,y(
ξ
k
)) denote an optimal solution to the pairs subproblem and z
k
the
optimal objective value z
P
( ¯x
k
, ¯y
k
,y(
ξ
k
)) . We may see the pairs subproblem as a
stochastic programming problem with two possible realizations
ξ
r
and
ξ
k
, with
probability p
r
and 1 − p
r
, respectively.
Two particular cases of the pairs subproblem are of interest. First, observe that
z
P
(x,
ξ
r
,
ξ
r
) is well-defined and is in fact z(x,
ξ
r
) , the deterministic problem for
which the only scenario is the reference scenario. Next, observe that if the reference
scenario is not a possible scenario, p
r
= P(ξ =
ξ
r
)=0,then z
P
(x,
ξ
r
,
ξ
k
) becomes
simply z(x,
ξ
k
) .
We now show the relations between the pairs subproblems and the recourse prob-
lem. To do this, we define the sum of pairs expected values, denoted by SPEV ,to
be
SPEV =
1
1 −p
r
K
∑
k=1
p
k
minz
P
(x,
ξ
r
,
ξ
k
) .
Again, observe that this definition still makes sense when scenario r is not possible.
In that case, however, it is not really a new concept.
Proposition 6. When the reference scenario is not in
Ξ
, then SPEV = WS .
Proof: As we observed before, when p
r
= 0 , the pairs subproblems z
P
(x,
ξ
r
,
ξ
k
)
coincide with z(x,
ξ
k
) . Hence, SPEV =
K
∑
k=1
k=r
p
k
minz(x,
ξ
k
) , which by definition
(1.2)is WS .
4.6 Bounds on EVPI and VSS 173
In general, the SPEV is related to WS and RP as follows.
Proposition 7. WS ≤ SPEV ≤ RP .
Proof: Let us first prove the first inequality. By definition,
SPEV =
K
∑
k=1
k=r
p
k
(c
T
¯x
k
+ p
r
q
T
¯y
k
+(1 − p
r
)q
T
y(
ξ
k
))
1 −p
r
,
where ( ¯x
k
, ¯y
k
,y(
ξ
k
)) is a solution to the pairs subproblem of
ξ
r
and
ξ
k
.Bythe
constraint definition in the pairs subproblem, the solution ( ¯x
k
, ¯y
k
) is feasible for the
problem z(x,
ξ
r
) so that
c
T
¯x
k
+ q
T
¯y
k
≥ minz(x,
ξ
r
)=z
∗
r
.
Weighting c
T
x
k
with a p
r
and a (1 − p
r
) term, we obtain:
SPEV =
K
∑
k=1
k=r
p
k
[p
r
(c
T
¯x
k
+ q
T
¯y
k
)+(1 − p
r
)(c
T
¯x
k
+ q
T
y(
ξ
k
))]
1 −p
r
,
which, by the property just given, is bounded by
SPEV ≥
∑
k=r
p
k
· p
r
·z
∗
r
1 −p
r
+
∑
k=r
p
k
(c
T
¯x
k
+ q
T
y(
ξ
k
)) .
Now, we simplify the first term and bound c
T
¯x
k
+ q
T
y(
ξ
k
) by z
∗
k
in the second
term, because ( ¯x,y(
ξ
k
)) is feasible for minz(x,
ξ
k
)=z
∗
k
. Thus,
SPEV ≥ p
r
z
∗
r
+
∑
k=r
p
k
z
k
∗
= WS .
For the second inequality, let x
∗
,y
∗
(
ξ
k
),k = 1,...,K, be an optimal solution to the
recourse problem. For simplicity, we assume here that r ∈
Ξ
. By the constraint
definitions, (x
∗
,y
∗
(
ξ
r
),y
∗
(
ξ
k
)) is feasible for the PAIRS subproblem of
ξ
r
and
ξ
k
. This implies
c
T
¯x
k
+ p
r
q
T
¯y
k
+(1 − p
r
)q
T
y(
ξ
k
) ≤ c
T
x
∗
+ p
r
q
T
y
∗
(
ξ
r
)+(1 − p
r
)q
T
y
∗
(
ξ
k
) .
If we take the weighted sums of these inequalities for all k = r , with p
k
as the
weight of the k th inequality, the weighted sum of the left-hand side elements is, by
definition, equal to (1 − p
r
) ·SPEV and the weighted sum of the right-hand side
elements is
K
∑
k=1
k=r
p
k
(c
T
x
∗
+ p
r
q
T
y
∗
(
ξ
r
)+(1 − p
r
)q
T
y
∗
(
ξ
k
))