Birge J.R., Louveaux F. Introduction to Stochastic Programming
Подождите немного. Документ загружается.
104 3 Basic Properties and Theory
where c is a known vector in ℜ
n
1
, b a known vector in ℜ
m
1
, A and W are
known matrices of size m
1
×n
1
and m
2
×n
2
, respectively, and W is called the
recourse matrix, which we assume here is fixed. This allows us to characterize the
feasibility region in a convenient manner for computation. If W is not fixed, we
may have difficulties, as shown next.
For each
ω
, T(
ω
) is m
2
×n
1
, q(
ω
) ∈ ℜ
n
2
and h(
ω
) ∈ ℜ
m
2
. Piecing to-
gether the stochastic components of the problem, we obtain a vector
ξ
T
(
ω
)=
(q(
ω
)
T
,h(
ω
)
T
,T
1·
(
ω
),...,T
m
2
·
(
ω
)) with N = n
2
+ m
2
+(m
2
×n
1
) components,
where T
i·
(
ω
) is the i -th row of the technology matrix T(
ω
) . As before, E
ξ
rep-
resents the mathematical expectation with respect to ξ . Let also
Ξ
⊆ ℜ
N
be the
support of ξ , i.e., the smallest closed subset in ℜ
N
such that P{ξ ∈
Ξ
} = 1.As
said in Section 2.4, the constraints are assumed to hold almost surely.
Problem (1.1) is equivalent to the so-called deterministic equivalent program
(DEP):
minz = c
T
x + Q(x)
s. t. Ax = b ,
x ≥0 ,
(1.2)
where
Q(x)=E
ξ
Q(x,
ξ
(
ω
)) (1.3)
and
Q(x,
ξ
(
ω
)) = min
y
{q(
ω
)
T
y |Wy = h(
ω
) −T(
ω
)x , y ≥ 0} . (1.4)
Examples of formulations (1.1)and(1.2)–(1.4) have been given in Chapter 1.Inthe
farmer’s problem, x represents the surfaces devoted to each crop, ξ represents the
yields so that only the technology matrix T(
ω
) is stochastic (because prices q and
requirements h are fixed), and y represents the sales and purchases of the various
crops. Formulations (1.1)and(1.2)–(1.4) apply for both discrete and continuous
random variables. Examples with continuous random yields have also been given
for the farmer’s problem.
This representation clearly illustrates the sequence of events in the recourse prob-
lem. First-stage decisions x are taken in the presence of uncertainty about future
realizations of ξ . In the second stage, the actual value of ξ becomes known and
some corrective actions or recourse decisions y can be taken. First-stage decisions
are, however, chosen by taking their future effects into account. These future effects
are measured by the value function or recourse function, Q(x) , which computes
the expected value of taking decision x .
When T is nonstochastic, the original formulation (1.2)–(1.4) can be replaced
by
minz = c
T
x +
Ψ
(
χ
)
3.1 Two-Stage Stochastic Linear Programs with Fixed Recourse 105
s. t. Ax = b ,
Tx−
χ
= 0 ,
x ≥ 0 ,
(1.5)
where
Ψ
(
χ
)=E
ξ
ψ
(
χ
,
ξ
(
ω
)) and
ψ
(
χ
,
ξ
(
ω
)) = min{q(
ω
)
T
y | Wy = h(
ω
) −
χ
, y ≥ 0}. This formulation stresses the fact that choosing x corresponds to gen-
erating an m
2
-dimensional tender
χ
= Tx to be bid against the outcomes h(
ω
) of
the random events.
The difficulty inherent in stochastic programming clearly lies in the computa-
tional burden of computing Q(x) for all x in (1.2)–(1.4), or
Ψ
(
χ
) for all
χ
in
(1.5). It is no surprise therefore that the properties of the deterministic equivalent
program in general and of the functions Q(x) or
Ψ
(
χ
) have been extensively
studied. The next sections present some of the known properties.
b. Discrete random variables
We now present some basic properties when ξ is a discrete random variable. This
is an important class of random variables. It is widely used in applications, either
directly or through sampling of a continuous distribution. The properties presented
in this section are used in Section 5.1 for the algorithmic solution of (1.2)–(1.4).
Let K
1
= {x | Ax = b , x ≥ 0} be the set determined by the fixed constraints,
namely those that do not depend on the particular realization of the random vector.
For any given
ξ
, we may define a so-called “elementary feasibility set” as
K
2
(
ξ
)={x | y ≥0existss. t. W(
ω
)y = h(
ω
) −T(
ω
)x}.
Example 1
Consider the following second-stage program
min 2y
1
+ y
2
s. t. y
1
+ 2y
2
≥ ξ
1
−x
1
,
y
1
+ y
2
≥ ξ
2
−x
1
−x
2
,
0 ≤ y
1
≤ 1 , 0 ≤y
2
≤ 1 .
Using the upper bounds on y , the first constraint implies ξ
1
−x
1
≤ 3andthe
second one implies ξ
2
−x
1
−x
2
≤ 2 . Thus, K
2
(
ξ
)={x | x
1
≥ ξ
1
−3 , x
1
+ x
2
≥
ξ
2
−2}.
As ξ is discrete, we may easily define the second-stage feasibility set
106 3 Basic Properties and Theory
K
2
=
ξ
∈
Ξ
K
2
(
ξ
) .
In Example 1, if ξ
1
takes the value 2 , 3 , 4 and ξ
2
the values 1 , 4 , 7 with
some nonspecified probabilities, independently of each other or not, K
2
= {x |x
1
≥
1 , x
1
+ x
2
≥ 5} . In fact, it suffices here to know the componentwise maximum of
ξ to obtain K
2
. This set is a polyhedron.
Define posW = {t |Wy = t , y ≥ 0}. It is called the positive hull of W .Itrepre-
sents the set of right-hand sides that can be obtained by a non-negative combination
of the columns of W . The positive hull is easily seen to be a convex cone .
Theorem 1.
a. For a given
ξ
, the elementary feasibility set K
2
(
ξ
) is a convex polyhedron.
b. When
ξ
is a finite discrete random variable, K
2
is a convex polyhedron.
Proof:
a. Consider some x and
ξ
such that no y ≥ 0 exists such that W(
ω
)y =
h(
ω
) −T(
ω
)x . Using the notation posW , it is the same to say that we con-
sider some x and
ξ
such that h(
ω
) −T(
ω
)x /∈ posW (
ω
) . Thus, we have a point,
h(
ω
) − T(
ω
)x , which does not belong to a convex set, posW(
ω
) . Then, there
must exist some hyperplane, say {x |
σ
T
x = 0}, that separates h(
ω
)−T(
ω
)x from
posW(
ω
) . This hyperplane satisfies
σ
T
t < 0fort ∈ posW (
ω
) and
σ
T
(h(
ω
) −
T(
ω
)x) > 0 . For one particular
ξ
, W(
ω
) is fixed and there can be only finitely
many different such hyperplanes which completes the proof.
b. The intersection of finitely many convex polyhedra is a convex polyhedron.
Efficient ways to obtain the separating hyperplanes (and more generally to obtain
K
2
) are presented in Chapter 5.
For fixed value of x and
ξ
,thevalue Q(x,
ξ
) of the second-stage program is
given by
Q(x,
ξ
)=min
y
{q(
ω
)
T
y |W(
ω
)y = h(
ω
) −T(
ω
)x , y ≥0} . (1.6)
Difficulties may arise when the mathematical program (1.6) is unbounded below
or infeasible. Unboundedness typically results of an ill-defined model and can easily
be avoided by adding upper bounds on y . Infeasibility is avoided if we only consider
x ∈ K
2
. Thus, for x ∈K
2
, Q(x,
ξ
) is finite for all
ξ
and we may define
Q(x)=E
ξ
Q(x,ξ)=
K
∑
k=1
p
k
Q(x,
ξ
k
)
where k = 1,...,K represents the K realizations of ξ . If wanted, the deterministic
equivalent program can be rewritten as
min z(x)=c
T
x + Q(x)
3.1 Two-Stage Stochastic Linear Programs with Fixed Recourse 107
s. t. x ∈K
1
∩K
2
.
We now study the properties of the second-stage value function.
Theorem 2. For a given
ξ
, the value function Q(x,
ξ
) is
(a) a piecewise linear convex function in (h,T) ;
(b) a piecewise linear concave function in q ;
(c) a piecewise linear convex function in x for all x ∈K
2
.
When ξ is a finite discrete random variable, Q(x) is piecewise linear and convex
on K
2
.
Proof: To prove convexity in (a) and (c), we just need to prove that f (b)=
min{q
T
y |Wy = b} is a convex function in b . We consider two different vectors,
say b
1
and b
2
, and some convex combination b
λ
=
λ
b
1
+(1 −
λ
)b
2
,
λ
∈(0,1) .
Let y
∗
1
and y
∗
2
be some optimal solution of min{q
T
y |Wy = b} for b = b
1
and
b = b
2
, respectively. Then,
λ
y
∗
1
+(1 −
λ
)y
∗
2
is a feasible solution of min{q
T
y |
Wy = b
λ
}.Now,let y
∗
λ
be an optimal solution of this last problem. We thus have
f (b
λ
)=q
T
y
∗
λ
≤ q
T
(
λ
y
∗
1
+(1 −
λ
)y
∗
2
)
=
λ
q
T
y
∗
1
+(1 −
λ
)q
T
y
∗
2
=
λ
f (b
1
)+(1 −
λ
) f (b
2
) ,
which proves the required proposition. A similar proof can be given to show con-
cavity in q . To prove piecewise linearity, observe that solving (1.6) for given x
and
ξ
amounts to finding some square submatrix B(
ω
) of W(
ω
) , called a basis
(see Section 2.11), such that y
B
= B(
ω
)
−1
(h(
ω
) −T(
ω
)x , y
N
= 0,where y
B
is
the subvector associated with the columns of B and y
N
includes the remaining
components of y . A basis is feasible if y
B
≥ 0 and a feasible basis is optimal if
a
B
(
ω
)
T
B(
ω
)
−1
W(
ω
) ≤q(
ω
)
T
. As long as these conditions hold, we have
Q(x,
ξ
)=q
B
(
ω
)
T
B(
ω
)
−1
(h(
ω
) −T(
ω
)x) ,
which is linear in q , h , T and x on a domain defined by the feasibility and op-
timality conditions. Piecewise linearity follows from the existence of finitely many
different optimal bases for the second-stage program. An alternative proof of piece-
wise linearity of the value function of a linear program can be obtained through the
method of projections (see Martin [1999, Corollary 2.49]).
Property (c) is important in practice. It is used in Section 5.1 for the algorithmic
solution of (1.2)–(1.4).
Example 2
Consider the following second-stage program:
108 3 Basic Properties and Theory
min 2y
1
+ y
2
s. t. y
1
+ y
2
≥ 1 −x
1
,
y
1
≥
ξ
−x
1
−x
2
,
y
1
,y
2
≥ 0 .
To reduce the calculations, assume 0 ≤x
1
≤1, 0≤x
2
≤1 . The optimal second-
stage solutions are as follows:
i. if
ξ
≤ x
1
+ x
2
⇒ y
1
= 0, y
2
= 1 −x
1
;
ii. if
ξ
> x
1
+ x
2
⇒ y
1
=
ξ
−x
1
−x
2
and y
2
=(1 −
ξ
+ x
2
)
+
where a
+
=
max(a,0) .
This results in three situations (as 1−
ξ
+x
2
may be positive or negative).Setting
the second-stage decisions into the second-stage objective, one obtains the following
three pieces for Q(x,
ξ
) :
Q(x,
ξ
)=
⎧
⎪
⎨
⎪
⎩
1 −x
1
for 0 ≤
ξ
< x
1
+ x
2
,
ξ
+ 1 −2x
1
−x
2
for x
1
+ x
2
≤
ξ
≤ 1 + x
2
,
2(
ξ
−x
1
−x
2
) for 1 + x
2
≤
ξ
.
Thus Q(x,
ξ
) is clearly piecewise linear in x . The proof of the convexity of
this particular Q(x,
ξ
) is left as part of Exercise 4. In this example, h(
ξ
)=
ξ
and
Q(x,
ξ
) is one-dimensionalin
ξ
. Convexity in
ξ
can be established in any classical
way.
Another property is evident from parametric solutions of linear programs when
q and T arefixed.Noticethat
Q(x,[q,
λ
(h
)+Tx,T ]) =
λ
Q(x,[q,h
+ Tx,T ]) (1.7)
for any
λ
≥0 because a dual optimal solution for h = h
+ Tx is also dual feasible
for h =
λ
(h
)+Tx and complementary with y
∗
optimal for h = h
+ Tx.Be-
cause
λ
y
∗
is also feasible for h =
λ
(h
)+Tx,
λ
y
∗
is optimal for h =
λ
(h
)+Tx,
demonstrating (1.7). This says that Q(x,[q,h
+Tx, T ]) is a positively homogeneous
function of h
. From the convexity of Q(x,[q,h
+Tx,T ]) in h = h
+Tx, this func-
tion is also sublinear (see Theorem 4.7 of Rockafellar [1969]) in h
. This property
is central to some bounding procedures described in Chapter 8.
Complete descriptions of Q(x,
ξ
) are also often useful. Finding the distribu-
tion induced on Q(x,
ξ
) is often the goal of these descriptions. This information
can then be used to find Q or to address other risk criteria that may not be given
by the expectation functional (e.g., the probability of losing some percentage of
one’s wealth). The description of the distribution of Q(x,
ξ
) is called the distribu-
tion problem. Its solution is quite difficult although some methods exist (see Wets
[1980b] and Bereanu [1980]). Approximations are generally required as in Demp-
ster and Papagaki-Papoulias [1980]; because these results are not central to our so-
lution development, we will not go into further detail.
We now present some of the results when ξ is not a discrete random variable.
3.1 Two-Stage Stochastic Linear Programs with Fixed Recourse 109
c. General cases
For fixed value of x and
ξ
, the value of the second-stage program is, as before,
given by (1.6)
Q(x,
ξ
)=min
y
{q(
ω
)
T
y |W(
ω
)y = h(
ω
) −T(
ω
)x , y ≥0} .
When the mathematical program (1.6) is unbounded below or infeasible, the value of
the second-stage program is defined to be −∞ or +∞ , respectively. The expected
second-stage value is, as given in (1.3)
Q(x)=E
ξ
Q(x,ξ).
Typically, the definition is made complete by adopting the convention +∞ +
(−∞)=+∞ . This corresponds to a conservative attitude, rejecting any first-stage
decision that could lead to an undefined recourse action for some realization even if
some other realization would induce an infinitely low-cost. It also reflects the fact
that second-stage programs can easily be bounded by bounding y , while infeasibil-
ities may be inherent to the problem.
For any given
ξ
, we may define a so-called “elementary feasibility set” as
K
2
(
ξ
)={x |Q(x,
ξ
) < ∞}
or, as before,
K
2
(
ξ
)={x | y ≥0existss. t. W(
ω
)y = h(
ω
) −T(
ω
)x}.
Both definitions are equivalent for a given
ξ
and enjoy the properties of Theo-
rem 1. When
ξ
is not a discrete random variable, we may now define K
2
in two
different ways:
K
2
= {x | Q(x) < ∞}
or
K
P
2
=
ξ
∈
Ξ
K
2
(
ξ
) .
The set K
P
2
is said to define the possibility interpretation of the second-stage
feasibility set. A first-stage decision x belongs to K
P
2
if, for “all possible” values
of the random vector ξ , a feasible second-stage decision can be taken. We now
illustrate that the two sets, K
2
and K
P
2
, can indeed be different when the random
variable is a continuous random variable.
Consider an example where the second stage is defined by
Q(x,
ξ
)=min
y
{y |
ξ
y = 1 −x , y ≥0}
110 3 Basic Properties and Theory
where ξ has a triangular distribution on [0,1] , namely, P(ξ ≤ u)=u
2
. Note that
here W reduces to a 1 ×1 matrix and is the only random element.
For all
ξ
in (0,1] , the optimal y is
1−x
ξ
,sothat
K
2
(
ξ
)={x |x ≤ 1}
and
Q(x,
ξ
)=
1 −x
ξ
, for x ≤1 .
When
ξ
= 0,no y exists such that 0·y = 1 −x , unless x = 1,sothat
K
2
(0)={x |x = 1} .
Now, for x = 1, Q(x,0) should normally be +∞ . However, because the probabil-
ity that ξ = 0 is zero, the convention is to take Q(x,0)=0 . This corresponds to
defining 0 ·∞ = 0.
Hence,
K
P
2
= {x | x = 1}∩{x | x ≤ 1} = {x |x = 1}
while
Q(x)=
1
0
1 −x
ξ
·2
ξ
d
ξ
= 2(1 −x) for all x ≤ 1,
so that K
2
= {x |x ≤1} and K
P
2
is strictly contained in K
2
. The difference between
the two sets relates to the fact that a point is not in K
P
2
as soon as it is infeasible
for some
ξ
value, regardless of the distribution of ξ , while K
2
does not consider
infeasibilities occurring with zero probability.
Fortunately, this kind of difficulty rarely occurs for programs with a fixed W
matrix. It never occurs when the random vector satisfies some conditions.
Another difficulty that could arise and would cause the sets K
P
2
and K
2
to be
different, would be to have Q(x,
ξ
) bounded above with probability one and yet to
have Q(x) , the expectation of Q(x,
ξ
) , unbounded.
Proposition 3. If ξ has finite second moments, then
P(
ω
| Q(x,ξ) < ∞)=1 implies Q(x) < ∞.
To illustrate why this might be true, consider particular x and
ξ
values. The
second-stage program is the linear program
Q(x,ξ)=min{q(
ω
)
T
y |Wy = h(
ω
) −T(
ω
)x,y ≥0}.
As discussed in the proof of Theorem 2, solving this linear program for given x and
ξ
amounts to finding some optimal basis B for which we have
Q(x,ξ)=q
B
(
ω
)
T
B
−1
(h(
ω
) −T(
ω
)x) .
3.1 Two-Stage Stochastic Linear Programs with Fixed Recourse 111
Now, assume Q(x,ξ) is bounded above with probability one and imagine for a
while that the same basis B would be optimal for all x and all
ξ
. Then, ξ having
finite second moments is a sufficient condition for Q(x) to be bounded because it
implies E
ξ
(q
T
B
B
−1
h) and E
ξ
(q
T
B
B
−1
Tx) are both bounded above. In general the
optimal basis B is different for different x and ξ values so that a more general
proof taking care of different submatrices of W is needed. This is done in detail in
Walkup and Wets [1967].
Theorem 4. For a stochastic program with fixed recourse where ξ has finite second
moments, the sets K
2
and K
P
2
coincide.
Proof: (Note: This proof uses some concepts from measure theory.) First consider
x ∈ K
P
2
. This implies Q(x,ξ) < ∞ with probability one, so that, by Proposition 3,
Q(x) is bounded above and x ∈K
2
.
Now, consider x ∈ K
2
. It follows that {
ξ
| Q(x,ξ) < ∞} is a set of measure
one. Observe that Q(x,
ξ
) < ∞ is equivalent to h(
ω
) −T (
ω
)x ∈ posW and that
h(
ω
) −T(
ω
)x is a linear function of
ξ
,and { ξ ∈
∑
| Q(x,ξ) < ∞} is a closed
subset of
∑
of measure one, for any set
∑
of measure one. In particular, {ξ ∈
Ξ
|
Q(x,ξ) < ∞} is a closed subset of
Ξ
having measure one. By definition of
Ξ
,this
set can only be
Ξ
itself, so that {
ξ
| Q(x,
ξ
) < ∞}⊆
Ξ
and therefore x ∈K
P
2
.
Note however that W beingfixedand ξ having finite moments are just sufficient
conditions for K
2
and K
P
2
to coincide. Other, more general, sufficient conditions
can be found in Walkup and Wets [1967].
Note also that a third definition of the second-stage feasibility set could be given
as {x | Q(x,ξ) < ∞ with probability one}. For problems with fixed recourse where
ξ has finite second moments, this set also coincides with K
2
and K
P
2
.Inthefol-
lowing, we simply speak of K
2
, the second-stage feasibility set.
Theorem 5. When W is fixed and ξ has finite second moments:
(a) K
2
is closed and convex.
(b) If T is fixed, K
2
is polyhedral.
(c) Let
Ξ
T
be the support of the distribution of T .If h(ξ) and T(ξ) are inde-
pendent and
Ξ
T
is polyhedral, then K
2
is polyhedral.
Proof: The proof of (a) is elementary under the possibility representation of K
2
.
If T is fixed, x ∈ K
2
if and only if h(
ξ
) −Tx∈ posW for all
ξ
∈
Ξ
h
,where
Ξ
h
is the support of the distribution of h(
ξ
) .
Consider some x and
ξ
s.t. h(
ξ
) −Tx ∈ posW . Then there must exist some
hyperplane, say {x |
σ
T
x = 0} that separates h(
ξ
) −Tx from posW . This hy-
perplane must satisfy
σ
T
t ≤ 0fort ∈ posW and
σ
T
(h(
ξ
) −Tx) > 0 . Because
W is fixed, there need only be finitely many different such hyperplanes, so that
112 3 Basic Properties and Theory
h(
ξ
) − Tx ∈ posW is equivalent to W
∗
(h(
ξ
) −Tx) ≤ 0 for some matrix W
∗
.
This matrix, called the polar matrix of W , is obtained by choosing some min-
imal set of separating hyperplanes. The set is minimal if removing any hyper-
plane would no longer guarantee the equivalence between h(
ξ
) −Tx ∈ posW and
W
∗
(h(
ξ
) −Tx) ≤ 0forallx and
ξ
in
Ξ
h
. It follows that x ∈ K
2
if and only if
W
∗
(h(
ξ
) −Tx) ≤ 0forall
ξ
in
Ξ
. This can still be an infinite system of linear
inequalities due to h(
ξ
) . We may, however, replace this system by
(W
∗
T)
i·
x ≥u
∗
i
= sup
h(
ξ
)∈
Ξ
h
W
∗
i·
h(
ξ
) , i = 1,...,l , (1.8)
where W
∗
i·
is the i -th row of W
∗
and l is the finite number of rows of W
∗
.
If for some i , u
∗
i
is unbounded, then the problem is infeasible and the result in
(b) is trivially satisfied. If, for all i , u
∗
i
< ∞ , then the system (1.8) constitutes a
finite system of linear inequalities defining the polyhedron K
2
= {x |W
∗
Tx≥ u
∗
}
where u
∗
is the vector whose i th component is u
∗
i
. This proves (b). When T is
stochastic, a relation similar to (1.8) holds, which, unless
Ξ
T
is finite, defines an
infinite system of inequalities. Whenever
Ξ
T
is polyhedral, (c) can be proved by
working on the extremal elements of
Ξ
T
. This is done in Wets [1974, Corollary
4.13].
We now turn to the properties of Q(x,
ξ
) , assuming it is not −∞ . First, observe
that Q(x,
ξ
) enjoys all the properties of Theorem 2.
Theorem 6. For a stochastic program with fixed recourse where ξ has finite second
moments,
(a) Q (x) is a Lipschitzian convex function and is finite on K
2
.
(b) If F(ξ) is an absolutely continuous distribution, Q(x) is differentiable on
riK
2
.
Proof: Convexity and finiteness in (a) are immediate. A proof of the Lipschitz
condition can be found in Wets [1972] or Kall [1976], who also give conditions for
Q(x) to be differentiable.
Although many of the proofs of these results become intricate in general, the out-
comes are relatively easy to apply.
When the random variables are appropriately described by a finite distribution,
the constraint set K
2
is best defined by the possibility interpretation and is easily
seen to be polyhedral. The second-stage recourse function Q(x) is piecewise linear
and convex on K
2
. The decomposition techniques of Chapter 5 then apply. This is
a category of programs for which computational methods can be made efficient, as
we shall see.
When the random variables cannot be described by a finite distribution, they can
usually be associated with some probability density. Many common probability den-
sities are absolutely continuous and have finite second moments; so, the constraints
set definitions K
2
and K
P
2
coincide and the second-stage value function Q(x) is
3.1 Two-Stage Stochastic Linear Programs with Fixed Recourse 113
differentiable and convex. Classical nonlinear programming techniques could then
be applied. A typical example was given in the farmer’s problem in Chapter 1.There,
a convex differentiable function Q(x) was constructed analytically. It is easily un-
derstood that analytical expressions can reasonably be found only for small second-
stage problems or problems with a very specific structure such as separability.
In general, one can only compute Q(x) by numerical integration of Q(x,ξ) ,
for a given value of x . Most nonlinear techniques would also require the gradients
of Q(x) , which in turn require numerical integration. An introduction to numerical
integration appears in Chapter 8. From there, we come to the conclusion that nu-
merical integration, as of today, produces an effective computational method only
when the random vector is of small dimensionality. As a consequence, the practical
solution of stochastic programs having continuous random variables is, in general, a
difficult problem. One line of approach is to approximate the random variable by a
discrete one and let the discretization be finer and finer, hoping that the solutions of
the successive problems with discrete random variables will converge to the optimal
solution of the problem with a continuous random variable. This is also discussed
in Chapter 8. It is sufficient at this point to observe that approximation is a second
reason for constructing efficient methods for stochastic programs with finite random
variables.
d. Special cases: relatively complete, complete, and simple recourse
The previous sections presented properties for general problems. In particular in-
stances, the feasible regions and objective values have special properties that are
particularly useful in computation. One advantage can be obtained if every solution
x that satisfies the first-period constraints, Ax = b , also has a feasible completion
in the second stage. In other words, K
1
⊂K
2
. In this case, we say that the stochastic
program has relatively complete recourse. If, for the example with stochastic W in
Section 3.1b., we had the first-period constraints x ≤ 1 , then this problem would
have relatively complete recourse.
Although relatively complete recourse is very useful in practice and in many of
the theoretical results that follow, it may be difficult to identify because it requires
some knowledge of the sets K
1
and K
2
. A special type of relatively complete
recourse may, however, often be identified from the structure of W . This form,
called complete recourse, holds when there exists y ≥ 0 such that Wy = t for all
t ∈ℜ
m
2
.
Complete recourse is also represented by posW = ℜ
m
2
(the positive cone
spanned by the columns of W includes ℜ
m
2
), and says that W contains a pos-
itive linear basis of ℜ
m
2
. Complete recourse is often added to a model to ensure
that no outcome can produce infeasible results. With most practical problems, this
should be the case. In some instances, complete recourse may not be apparent. An
algorithm in Wets and Witzgall [1967] can be used in this situation to determine
whether W contains a positive linear basis.