Birge J.R., Louveaux F. Introduction to Stochastic Programming

Подождите немного. Документ загружается.

124 3 Basic Properties and Theory

where h,t are uniformly distributed on the unit circle, h

≤1.Find Q(x)

and show that it is not eventually linear for x →∞ (Wets [1974]).

10. Show that E

∂

Q(x,

(

)) is given by (1.18).

11. Show that an optimal solution (

∗

(

)) to the dual program in (1.19)pro-

vides a solution to the optimality conditions in (1.17)using(1.18) and that the

optimal objective value v

∗

is the same as the optimal value z

∗

in (1.2).

12. Suppose you wish to solve (1.11) in the form of (1.20) over (x(

),y(

))

∈L

∞

(

,B,

: ℜ

) . What is the optimal value? How does this differ from

using (1.2)?

13. This exercise uses approximation results to give an alternative proof of The-

orem 13. As shown in Chapter 8, if a discrete distribution approaches a con-

tinuous distribution (in distribution) and problem (1.2) has a bounded optimal

solution and the bounded second moment property, then a limiting optimal so-

lution for the discrete distributions is an optimal solution using the continuous

distribution. This also implies that recourse solutions, y

∗

, converge and that the

optimality conditions in (1.27)–(1.31) are obtained as long as the

k∗

in the

discrete approximations are uniformly bounded. Show that relatively complete

recourse implies uniform boundedness of some

k∗

for any discrete approxi-

mation approaching a continuous distribution in (1.18). (Hint: Construct a sys-

tem of equations that must be violated for some iteration

of the discretization

and for any bound M on the largest value of

k∗

if the

k∗

are not uniformly

bounded. Then show that the complementary system implies no relatively com-

plete recourse.)

3.2 Probabilistic or Chance Constraints

a. General case

As mentioned in Chapter 2, in some models, constraints need not hold almost surely

as we have assumed to this point. They can instead hold with some probability or

reliability level. These probabilistic,orchance, constraints take the form:

P{A

(

)x ≥h

(

)}≥

, (2.1)

where 0 <

< 1andi = 1,...,I is an index of the constraints that must hold

jointly. We can, of course, model these constraints in a general expectational form

( f

(

,x(

))) ≥

where f

is an indicator of {

| A

(

)x ≥ h

(

)} but we

would then have to deal with a discontinuous function.

In chance-constrained programming (see, e.g., Charnes and

Cooper [1963]), the objective is often an expectational functional as we used ear-

lier (the E-model), or it may be the variance of some result (the V-model)orthe

probability of some occurrence (such as satisfying the constraints) (the P-model).

3.2 Probabilistic or Chance Constraints 125

Another variation includes an objective that is a quantile of a random function (see,

e.g., Kibzun and Kurbakovskiy [1991] and Kibzun and Kan [1996]).

The main results with probabilistic constraints refer to forms of deterministic

equivalents for constraints of the form in (2.1). Provided the deterministic equiva-

lents of these constraints and objectives have the desired convexity properties, these

functions can be added to the recourse problems given earlier (or used as objectives).

In this way, all our previous results apply to chance-constrained programming with

suitable function characteristics.

The main goal in problems with probabilistic constraints is, therefore, to deter-

mine deterministic equivalents and their properties. To maintain consistency with

the recourse problem results, we let

(

)={x | P(A

(

)x ≥h

(

)) ≥

} , (2.2)

where 0 <

≤ 1and



(1)=K

as in Section 3.1. Unfortunately, K

(

)

need not be convex or even connected. Suppose, for example that

= {

]=P[

(

)=A

(



−1



(



−1



(



−3



(2.3)

for 0 <

≤

, K

(

)=[0, 1] ∪[2, 3] .

When each i corresponds to a distinct linear constraint and A

is a ﬁxed row

vector, then obtaining a deterministic equivalent of (2.2) is fairly straightforward.

In this case, P(A

x ≥ h

(

)) = F

x) ,where F

is the distribution function of

. Hence, K

(

)={x | F

x) ≥

}, which immediately yields a deterministic

equivalent form. In general, however, the constraints must hold jointly so that the set

I is a singleton. This situation corresponds to requiring an

-conﬁdence interval

that x is feasible. We assume this in the remainder of this section and drop the

superscript i indicating the set of joint constraints.

The results to determine the deterministic equivalent often involve manipulations

of probability distributions that use measure theory. The remainder of this section is

intended for readers familiar with this area. One of the main results in probabilistic

constraints is that, in the joint constraint case, a large class of probability measures

on h(

) (for A ﬁxed) leads to convex and closed K

(

) . A probability measure

P is in this class of quasi-concave measures if for any convex measurable sets U

and V and any 0 ≤

≤ 1,

P((1 −

)U +

V) ≥ min{P(U),P(V)} . (2.4)

126 3 Basic Properties and Theory

The use of this and a special form, called logarithmically concave measures,be-

gan with Pr´ekopa [1971, 1973]. General discussions also appear in Pr´ekopa [1980,

1995], Kallberg and Ziemba [1983] concerning related utility functions, and the

surveys of Wets [1983b, 1990] which include the following theorem.

Theorem 14. Suppose A is ﬁxed and h has an associated quasi-concave proba-

bility measure P . Then K

(

) is a closed convex set for 0 ≤

≤ 1 .

Proof:LetH (x)={h | Ax ≥ h}. Suppose x(

+(1 −

where

∈ K

(

) . Suppose h

∈H (x

) and h

∈H (x

) .Then

+(1 −

≤

Ax(

) ,so H (x(

)) ⊃

H (x

)+(1 −

)H (x

) . Hence, P({Ax(

) ≥ h})=

P(H (x(

)) ≥ P(

H (x

)+(1 −

)H (x

)) ≥

. Thus, K

(

) is convex.

For closure, suppose that x

→ ¯x ,where x

∈K

(

) . Consider H (x

) .If h ≤

for some subsequence {

} of {

},then h ≤A ¯x . Hence limsup

H (x

) ⊂

H ( ¯x) ,so P(H ( ¯x)) ≥ P(limsup

H (x

)) ≥ limsup

P(H (x

)) ≥

The relevance of this result stems from the large class of probability measures which

ﬁt these conditions. Some extent of this class is given in the following result of

Borell [1975], which we state without proof.

Theorem 15. If f is the density of a continuous probability distribution in ℜ

and f

−(

)

is convex on ℜ

, then the probability measure

P(B)=



f (x) dx ,

deﬁned for all Borel sets B in ℜ

is quasi-concave.

In particular, this result states that any density of the form f (x)=e

−l(x)

for some

convex function l yields a quasi-concave probability measure. These measures in-

clude the multivariate normal, beta, and Dirichlet distributions and are logarithmi-

cally concave (because, for 0 ≤

≤ 1, P((1 −

)U +

V) ≥ P(U)

P(V)

1−

for

all Borel sets U and V ) as studied by Pr´ekopa. These distributions lead to com-

putable deterministic equivalents as, for example, in the following theorem.

Theorem 16. Suppose A is ﬁxed and the components h

,i = 1,...,m

,of h are

stochastically independent random variables with logarithmically concave proba-

bility measures, P

, and distribution functions, F

,then K

(

{x |

∑

i=1

ln(F

i·

x)) ≥ ln

} and is convex.

Proof: From the independence assumption, P[Ax ≥ h]=

i=1

i·

x ≥ h

i=1

i·

x) .So, K

(

)={x |

i=1

i·

x) ≥

}. Taking logarithms (which is

a monotonically increasing function), we obtain K

(

)={x |

∑

i=1

ln(F

i·

x)) ≥

}. Because

i·

(

+(1 −

)) = P

≤ A

i·

(

+(1 −

))

≥ P

(

≤ A

i·

}+(1 −

){h

≤A

i·

)})

3.2 Probabilistic or Chance Constraints 127

≥ P

({h

≤ A

i·

})

({h

≤ A

i·

})

1−

= F

i·

)

i·

)

1−

the logarithm of F

i·

x) is a concave function, and K

(

) is convex.

Logarithmically concave distribution functions include the increasing failure rate

functions (see Miller and Wagner [1965] and Parikh [1968]) that are common in

reliability studies. Other types of quasi-concave measures include the multivariate

t and F distributions. Because these distributions include those most commonly

used in multivariate analysis, it appears that, with continuous distributions and ﬁxed

A , the convexity of the solution set is generally assured.

When A is also random, the convexity of the solution set is, however, not as

clear. The following theorem from Pr´ekopa [1974], given without proof, shows this

result for normal distributions with ﬁxed covariance structure across columns of A

and h .

Theorem 17. If A

1·

,...,A

,h have a joint normal distribution with a common

covariance structure, a matrix C , such that E[(A

i·

− E(A

i·

))(A

j·

−E(A

j·

))

]=r

Cfori, jin1,...,n

, and

E[(A

i·

−E(A

i·

))(h−E(h))] = s

for i = 1,...,n

,where r

and s

are constants for all i and j , then K

(

) is

convex for

≥

Stronger results than Theorem 17 are difﬁcult to obtain. In general, one must

rely on approximations to the deterministic equivalent that maintain convexity al-

though the original solution set may not be convex. We will consider some of these

approximations in Chapter 8.

Some other speciﬁc examples where A may be random include single constraints

(see Exercise 5). In the case of h ≡0 and normally distributed A , the deterministic

equivalent is again readily obtainable as in the following from Parikh [1968].

Theorem 18. Suppose that m

= 1 ,h

= 0 , and A

1·

has mean

1·

and covari-

ance matrix C

,then K

(

)={x |

1·

x −

−1

(

)



x ≥0} ,where

is the

standard normal distribution function.

Proof: Observe that A

1·

x is normally distributed with mean,

1·

x , and variance,

x .If x

x = 0 , then the result is immediate. If not, then

1·

x−

1·

√

is a stan-

dard normal random variable with cumulative

,and

P(A

1·

x ≥0)=P(

1·

x −

1·



≥

−

1·



)

= P(

1·

x −

1·



≤

1·



)

128 3 Basic Properties and Theory

(

1·



) .

Substitution in the deﬁnition of K

(

) yields the result.

Finally in this chapter, we would like to show some of the similarities between

models with probabilistic constraints and problems with recourse. As stated in

Chapter 2, models with probabilistic constraints and models with recourse can of-

ten lead to the same optimal solutions. Some other aspects of the modeling process

may favor one over the other (see, e.g., Hogan, Morris, and Thompson [1981, 1984],

Charnes and Cooper [1983]), but, these differences generally just represent decision

makers’ different attitudes toward risk.

We use an example from Parikh [1968] to relate simple recourse and chance-

constrained problems. Consider the following problem with probabilistic constraints:

min c

s. t. Ax = b ,

i·

x ≥ h

] ≥

, i = 1,...,m

x ≥ 0 ,

(2.5)

where P

is the probability measure of h

and F

is the distribution function for

. For the deterministic equivalent to (2.5), we just let F

∗

, to obtain:

min c

s. t. Ax = b ,

i·

x ≥h

∗

, i = 1,...,m

x ≥0 .

(2.6)

Suppose we solve (2.6) and obtain an optimal x

∗

and optimal dual solution

{

∗

},where c

∗

= b

∗

+ h

∗T

∗

.If

∗

= 0,let q

= 0 and, if

∗

> 0,

let q

∗

1−

. An equivalent stochastic program with simple recourse to (2.5)is

then:

min c

x + E

]

s. t. Ax = b ,

i·

x + y

−y

−

= h

, i = 1,...,m

x,y

−

≥ 0 .

(2.7)

For problems (2.5)and(2.7) to be equivalent, we mean that any x

∗

optimal in (2.5)

corresponds to some (x

∗

∗+

) optimal in (2.7) for a suitable deﬁnition of q

and

that any (x

∗

∗+

) optimal in (2.7) corresponds to x

∗

optimal in (2.5) for a suitable

deﬁnition of

. We show the ﬁrst part of this equivalence in the following theorem.

3.2 Probabilistic or Chance Constraints 129

Theorem 19. Fo r the q

deﬁned as a function of some optimal

∗

for the dual

to (2.5),if x

∗

is optimal in (2.5), there exists y

∗+

≥ 0 a.s. such that (x

∗

∗+

) is

optimal in (2.7).

Proof:First,letx

∗

be optimal in (2.5). It must also be optimal in (2.6) with dual

variables, {

∗

}.Wemusthave

∗

≥ 0,

−

∗T

A −

∗T

T ≥ 0 ,

∗

−h

∗

≥ 0 ,

−

∗T

A −

∗T

T)x

∗

= 0 ,

and

∗T

(Tx

∗

−h

∗

)=0 . (2.8)

Now, for x

∗

to be optimal in (2.7), consider the optimality conditions (1.13) from

Corollary 10. These conditions state that if there exists

∗

such that

−

∗T

A −

∑

i=1

i·

−q

i·

∗

)) ≥ 0 ,

−

∗T

A −

∑

i=1

i·

−q

i·

∗

)))x

∗

= 0 . (2.9)

Substituting for

∗

= q

(1 −

) in (2.8) and noting from the complementarity

condition that

= F

∗

)=F

i·

∗

) if

∗

> 0 , we obtain

−

∗T

A −

∗T

T = c

−

∗T

A −

∑

i=1

i·

(1 −F

i·

∗

)))

= c

−

∗T

A −

∑

i=1

i·

−q

i·

∗

)) (2.10)

from the deﬁnitions and noting that

∗

> 0 if and only if q

> 0.From(2.10), we

can verify the conditions in (2.9) and obtain the optimality of x

∗

in (2.7).

If we assume x

∗

is optimal in (2.7), we can reverse the argument to show that

∗

is also optimal in (2.5)forsomevalueof

. This result (from Symonds [1968])

is Exercise 7. Further equivalences are discussed in Gartska [1980]. We note that all

of these equivalences are somewhat weak because they require a priori knowledge

of the optimal solution to one of the problems (see also the discussion in Gartska

and Wets [1974]).

130 3 Basic Properties and Theory

Exercises

1. Suppose a single probabilistic constraint with ﬁxed A and that h has an expo-

nential distribution with mean

. What is the resulting deterministic equivalent

constraint for K

(

) ?

2. For the example in (2.3), what happens for

≤ 1?

3. Can you construct an example with continuous random variables where K

(

)

is not connected? (Hint: Try a multimodal distribution such as a random choice

of one of two bivariate normal random variables.)

4. Extend Theorem 14 to allow any set of convex constraints, g

(x,

(

)) ≤ 0,

i = 1,...,m .

5. Suppose a single linear constraint in K

(

) where the components of A and h

have a joint normal distribution. Show that K

(

) is also convex in this case for

≥

. (Hint: The random variable, A

1·

x −h

, is also normally distributed.)

6. Show that



x is a convex function of x .

7. Prove the converse of Theorem 19 by ﬁnding an appropriate

so that the x

∗

that is optimal in (2.7) is also optimal in (2.5).

8. Let

)={x|P{A(

)x ≥ h}≤

},where A(

) has a joint normal distribu-

tion as in Theorem 17 (and h is ﬁxed). Show that, in contrast to the result of

Theorem 17,

) need not be convex for any 0 <

< 1.

b. Probabilistic constraints with discrete random variables

(

) is a discrete random variable, there exists a ﬁnite number of scenarios

which correspond to the realizations of ξ . They are represented as

,...,

Scenario k has a probability p

with

∑

k=1

= 1.

Scenarios can be obtained through experts’ opinions. Another typical way to get

scenarios is when the information over the random variables comes from historical

data. The distribution of the random vector is then known as the empirical distribu-

tion.

Assume we have a constraint of the form

P{g(x,y(

),ξ(

)) ≤ 0}≥

. (2.11)

It is a joint probabilistic constraint as g(·) ≤ 0 may contain several constraints

under a vector representation. This includes classical cases such as g(x,y(

ξ(

)) = h(

) −Ax . This also includes cases where the probabilistic constraint de-

pends on the recourse actions. Then g(x, y(

),ξ(

))=h(

)−T (

)x−W(

)y(

) .

This exercise was suggested by Yue Rong, University of California at Riverside.

3.2 Probabilistic or Chance Constraints 131

Using the indicator function

(a)=0ifa ≤ 0 and 1 if at least one component

of a is strictly positive, the probabilistic constraint is equivalent to

∑

k=1

(g(x,y

)) ≤ 1 −

. (2.12)

The left-hand side of (2.12) sums up the probability of the scenarios for which

g(·) ≤ 0 is violated. Assume that for each scenario k , an upper bound vector u

can be found such that g(x, y

) ≤ u

for all feasible x , y

. Then, (2.12) can be

transformed into

∑

k=1

≤ 1 −

, (2.13)

g(x,y

) ≤ u

, k = 1...,K , (2.14)

∈{0,1}, k = 1,...,K . (2.15)

The binary variable w

plays the role of the indicator function. When

g(x,y

) ≤ 0, w

takes the value 0 . When at least one component of g(x,y

)

is strictly positive, then w

= 1 and scenario k contributes p

to the left-hand side

in (2.13).

The joint probabilistic constraint (2.11) with a discrete random variable is trans-

formed into a mixed integer programming (MIP) formulation. When g(·) is linear,

the stochastic program with probabilistic constraint is transformed into a mixed in-

teger linear program (MILP) and can be solved using your favorite MILP solver. We

now provide two examples of how (2.11) is transformed into (2.13)–(2.15). We then

give an introduction to reformulations of (2.13)–(2.15) that allow efﬁcient solutions

of large problems.

Example 3

Consider the example from Section 2.7a. We are asked to ﬁnd the numbers x

and

of seats in ﬁrst and business class for a plane of 200 seats. As in (2.11), assume

now a joint probabilistic constraint

P(x

≥ ξ

+ x

≥ ξ

+ ξ

) ≥0.95, (2.16)

where ξ

and ξ

represents the weekdays demands in ﬁrst and business class.

This corresponds to the classical case where g(x,y(

),ξ(

)) = h(

) −Ax , with

)

=(ξ

,ξ

+ ξ

) and A =





Assume now the random variables (ξ

,ξ

) are given by the empirical data of

last year. (These data must correspond to the number of calls and not to the number

of passengers, which may depend on the acceptance policy at that time). This creates

132 3 Basic Properties and Theory

an empirical distribution of 260 pairs (ξ

,ξ

) for each weekday of last year. Each

of the 260 pairs is a scenario of probability 1/260 .

In (2.14), we need an upper bound on ξ

−x

and on ξ

+ ξ

−x

for

each k . Here, it sufﬁces to take ξ

and ξ

+ ξ

, respectively. As an illustration, if

scenario k has demands (14,32) in ﬁrst and business, then the two corresponding

constraints in (2.14)are

14 −x

≤ 14w

46 −x

−x

≤ 46w

Thus, (2.16) is formulated using 260 binary variables w

’s, one constraint (2.13)

and 520 constraints in (2.14). To put it in more general terms, (2.16) is reformulated

using K extra binary variables and 2K + 1 extra constraints.

Example 4

Consider the farmer in Section 1.1. The example was built assuming a discrete ran-

dom variable with only three scenarios: good, fair, and bad. This number can easily

be extended either in a similar manner or by taking past observations of the yields.

We now assume K scenarios, each consisting of a vector of three yields.

The farmer ﬁnds it inappropriate to purchase large quantities of wheat and/or

corn. He considers it excessive to purchase more than a total of 20 T. Owing to

the uncertainty of mother nature, he allows for a 20% probability of excessive pur-

chases. Thus, his probabilistic constraint is

P(y

(

)+y

(

) ≤ 20) ≥ 0.80 (2.17)

where y

(

) and y

(

) are the purchases of wheat and corn, respectively.

Here is a case where the probabilistic constraint depends on the recourse actions

under the general form g(x, y(

),ξ(

)) = h(

) −T(

)x −W(

) y(

) .

To obtain (2.14), we start from the representation of the constraint under scenario

k as −20+y

≤0,where y

and y

represent the purchase of wheat and corn

under scenario k .FromTable1 in Section 1.1, the total requirement of wheat and

corn is 440 . The upper bound to form (2.14) is the value 420 , so that a single

constraint of the form

+ y

≤ 20 + 420w

(2.18)

is created. (If y

+ y

≤ 20 , then w

is 0 ; otherwise, w

= 1 and the constraint

imposes no limit on the purchase of wheat and corn as the total cannot exceed 440 .)

The recourse problem with K scenarios and the extra probabilistic constraint (2.17)

is reformulated as an MILP with K extra binary variables and K + 1 extra con-

straints.

3.2 Probabilistic or Chance Constraints 133

Improved formulation of a probabilistic constraint with discrete

random variables

For large values of K , the MILP may become difﬁcult to solve. This is due to the

structure of (2.14). It is indeed a weak constraint on w

. To see this, consider the

example of (2.18).

Suppose that the total purchase under scenario k is 30 . Then (2.18) is equivalent

to 420w

≥10 , or w

≥0.0238 . As (2.18) is the only constraint on w

, integrality

can only be recovered through branching. The MILP solver will have to branch on

all nonzero binaries, and none of them is likely to be spontaneously 1 . Moreover,

after some w

’s are ﬁxed by branching, additional w

’s may become fractional and

require extra branching.

It is classical then to search for efﬁcient valid inequalities. A valid inequality is

a linear constraint added to the original formulation, which does not eliminate any

integer solution but eliminates fractional solutions (see Appendix 2 of Chapter 7 for

some examples). A valid inequality provides a reformulation of the problem that

contains fewer fractional solutions but the same integer solutions.

To illustrate valid inequalities, we use the example of constraint (2.17) and its re-

formulation (2.18). As the probabilistic constraint only depends on corn and wheat,

we may restrict our attention for this analysis to the ﬁrst two components of the

random vector.

We may say that scenario k dominates scenario j if

≥

, where the in-

equality must hold componentwise. In the current farmer example, if scenario k

dominates scenario j , the yields of wheat and corn are higher in scenario k .It

follows that the purchases of both products can only be smaller under scenario k .

Hence, w

≤ w

. A ﬁrst set of potential valid inequalities is w

≤ w

for all pairs

of scenarios such that

≥

Now, we may deﬁne A

= {j |

≥

} as the dominance set of scenario k .

This dominance set includes k and all scenarios dominated by k . By the concept

of dominance, if w

= 1, then w

= 1, ∀j ∈ A

. An immediate consequence is

that w

= 0ifP(A

) >

,where P(A

∑

j∈A

More generally, if P(∪

k∈C

) >

,theset C forms a so-called cover for which

the following constraint is a valid inequality:

∑

k∈C

≤|C|−1,

where |C| denotes the cardinality of C . The terminology cover comes from the

knapsack structure of (2.13), a structure thoroughly studied in integer programming.

However, covers are generated here from the probability of the dominance sets A

instead of simply from the coefﬁcients p

We now illustrate the valid inequalities in the farmer problem with the extra

probabilistic constraint (2.17). Imagine the farmer is able to collect 25 scenarios,

each having probability 0.04 . (He may obtain them in a cooperative fashion with

some fellow farmers or get them from an agricultural research institute.)