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

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

Chapter 6

Multistage Stochastic Programs

As the Chapter 1 examples demonstrate, many operational and planning problems

involve sequences of decisions over time. The decisions can respond to realizations

of outcomes that are not known a priori. The resulting model for optimal decision

making is then a multistage stochastic program. In Section 3.4,wegavesomeofthe

basic properties of multistage problems. In this chapter, we explore the variety of

solution procedures that have been proposed speciﬁcally for multistage stochastic

programs.

In general, the methods for two-stage problems generalize to the multistage case

but include additional complications. Because of these difﬁculties, we will describe

only those methods that have shown some success for obtaining fully-optimal so-

lutions to problems in high dimension with a given ﬁnite set of possible scenarios.

As in previous chapters, the focus here is also on problems with time-separable

objectives (in contrast to the risk-sensitive utility in (10.7) of Chapter 2).

As stated in Section 3.4, the multistage stochastic linear program with a ﬁnite

number of possible future scenarios has a deterministic equivalent linear program.

However, as the graph in Figure 5 of Chapter 3 begins to suggest, the structure of

this problem is somewhat more complex than that of the two-stage problem. The

extensive form is not readily accessible to manipulations such as the factorizations

for extreme or interior point methods that were described in Chapter 5, although

some computational efﬁciencies are again possible as mentioned in Section 5.5.

Generally, some special structure is required for efﬁcient solution in the general

case since these problems are PSPACE-hard (Dyer and Stougie [2006]) and require

exponential effort in the horizon H for provably tight approximations with high

probability (Swamy and Shmoys [2005] and Shmoys and Swamy [2006]).

In general, a variety of approximation approaches to multistage problems are

possible, such as the following:

1. value function approximation: replacing Q

with some simpliﬁed representa-

tion, such as an outer or inner linearization;

2. constraint relaxation and dualization: relaxing constraints into a Lagrangian or

looking at dual forms that may not be implementable but may give bounds or

guidelines for implementable policies;

J.R. Birge and F. Louveaux, Introduction to Stochastic Programming, Springer Series 265

in Operations Research and Financial Engineering, DOI 10.1007/978-1-4614-0237-4

 Springer Science+Business Media, LLC 2011

266 6 Multistage Stochastic Programs

3. policy restriction: restricting the set of alternative actions to a simpliﬁed form

that allows for efﬁcient computation;

4. time, state, and path aggregation or scenario generation and reduction: starting

with a large set of possibilities and then combining (or selecting) them to form

more tractable representations;

5. Monte Carlo methods: sampling to obtain smaller, more tractable representa-

tions.

This chapter will focus on approaches to the ﬁrst two items above while the other

approaches that relate more directly to approximation and sampling methods appear

in Chapters 9 and 10. In Section 6.1, we describe the basic nested decomposition

procedures for multistage stochastic linear programs, which represents value func-

tion approximation with outer (or inner) linearization. Section 6.2 shows how this

approach extends to quadratic problems. Section 6.3 then considers the use of block

separability and special problem structures. Section 6.4 describes approaches for

multistage nonlinear problems based on constraint relaxation and the Lagrangian

approach.

6.1 Nested Decomposition Procedures

Nested decomposition procedures were proposed for deterministic models by Ho

and Manne [1974] and Glassey [1973]. These approaches are essentially inner lin-

earizations that treat all previous periods as subproblems to a current period master

problem. The previous periods generate columns that can be used by the current-

period master problem.

A difﬁculty with these primal nested decomposition or inner linearization meth-

ods is that the set of inputs may be fundamentally different for different last period

realizations. Because the number of last period realizations is the total number of

scenarios in the problem, these procedures are not well adapted to the bunching

procedures described in Section 5.4. Some success has been achieved, however, by

No¨el and Smeers [1987], as we will describe, by applying inner linearization to the

dual, which is again outer linearization of the primal problem.

The general primal approach is, therefore, to use an outer linearization built on

the two-stage L -shaped method. Louveaux [1980] ﬁrst performed this generaliza-

tion for multistage quadratic problems, as we discuss in Section 6.2. Birge [1985b]

extended the two-stage method in the linear case as in the following description.

The approach also appears in Pereira and Pinto [1985].

The basic idea of the nested L -shaped or Benders decomposition method is to

place cuts on Q

t+1

) in (3.4.3) and to add other cuts to achieve an x

that has a

feasible completion in all descendant scenarios. The cuts represent successive linear

approximations of Q

t+1

. Due to the polyhedral structure of Q

t+1

, this process

converges to an optimal solution in a ﬁnite number of steps.

6.1 Nested Decomposition Procedures 267

In general, for every stage t = 1,...,H −1 and each scenario at that stage, k =

1,...,K

we have the following master problem, which generates cuts to stage

t −1 and proposals for stage t + 1:

min (c

)

(1.1)

s. t. W

= h

−T

t−1

a(k)

, (1.2)

k, j

≥ d

k, j

, j = 1,...,r

, (1.3)

k, j

≥ e

k, j

, j = 1,...,s

, (1.4)

≥ 0 , (1.5)

where a(k) is the ancestor scenario of k at stage t −1, x

t−1

a(k)

is the current solution

from that scenario, and where for t = 1 , we interpret b = h

−T

as initial

conditions of the problem. We may refer also to the stage H problem in which

and constraints (1.3)and(1.4) are not present. To designate the period and scenario

of the problem in (1.1)–(1.5), we also denote this subproblem, NLDS(t,k) .

We ﬁrst describe a basic algorithm for iterating among these stages. We then dis-

cuss some enhancements of this basic approach. In the following, D

( j) denotes the

period t descendants of a scenario j at period t −1 . We assume that all variables

in (3.4.1) have ﬁnite upper bounds to avoid complications presented by unbounded

solutions (although, again, these can be treated as in Van Slyke and Wets [1969]).

Nested L -Shaped Method for Multistage Stochastic Linear Programs

Step 0.Set t = 1, k = 1, r

= s

= 0 , add the constraint

= 0to(1.1)–(1.5)for

all t and k ,andlet DIR = FORE .GotoStep1.

Step 1. Solve the current problem, NLDS(t,k) . If infeasible and t = 1 , then stop;

problem (3.4.1) is infeasible. If infeasible and t > 1 , then let r

t−1

a(k)

= r

t−1

a(k)

+ 1and

let DIR = BACK . Let the infeasibility condition (see Exercise 1) be obtained by a

dual basic solution,

≥ 0 , such that (

)

≤ 0but(

)

−

t−1

a(k)

)+(

)

> 0.Let D

t−1

a(k),r

t−1

a(k)

)

t−1

, d

t−1

a(k),r

t−1

a(k)

)

Let t = t −1, k = a(k) and return to Step 1.

If feasible, update the values of x

, and store the value of the complementary

basic dual multipliers on constraints (1.2)–(1.4)as (

) , respectively. If k <

,let k = k +1 , and return to Step 1. Otherwise, ( k = K

), if t = 1,set DIR =

FORE ;if DIR = FORE and t < H ,let t = t + 1 and return. If t = H ,let DIR =

BACK .GotoStep2.

Instead of a ﬁxed number of scenarios K as in the two-stage discussion, we use K

here to

represent the number of distinct scenarios at stage t to avoid confusion with K

which represents

the feasibility set at stage t . Later in the text, we also use K

to represent the conditional number

of outcomes at stage t , i.e., the maximum number of branches from a single node at stage t −1.

268 6 Multistage Stochastic Programs

Step 2.If t = 1,let t = t + 1, k = 1 and go to Step 1. Otherwise, for all scenarios

j = 1,...,K

t−1

at t −1 , compute

t−1

∑

k∈D

( j)

t−1

(

)

t−1

and

t−1

∑

k∈D

( j)

t−1

[(

)

∑

i=1

(

)

∑

i=1

(

)

] .

The current conditional expected value of all scenario problems in D

( j) is then

t−1

= e

t−1

−E

t−1

. If the constraint

t−1

= 0 appears in NLDS(t −1, j) ,

then remove it, let s

t−1

= 1 , and add a constraint (1.4) with E

t−1

and e

t−1

NLDS(t −1, j) .

t−1

,thenlet s

t−1

= s

t−1

+ 1 and add a constraint (1.4) with E

t−1

and e

t−1

to NLDS(t −1, j) .If t = 2 and no constraints are added to NLDS(1)

( j = K

= 1 ), then stop with x

optimal. Otherwise, let t = t −1, k = 1. If

t = 1,let DIR = FORE .GotoStep1.

Many alternative strategies are possible in this algorithm in terms of determin-

ing the next subproblem (1.1)–(1.5) to solve. For feasible solutions, the preceding

description explores all scenarios at t before deciding to move to t −1ort + 1.

For feasible iterations, the algorithm proceeds from t in the direction of DIR until

it can proceed no further in that direction. This is the “fast-forward-fast-back” pro-

cedure proposed by Wittrock [1983] for deterministic problems and implemented

with success by Gassmann [1990] for stochastic problems. One may alternatively

enforce a move from t to t −1 (“fast-back”) or from t to t + 1 (“fast-forward”)

whenever it is possible. From various experiments (e.g., Gassmann [1990], Morton

[1996], and Birge et al. [1996]), fast-forward-fast-back sequencing protocol seems

generally more efﬁcient than the alternatives.

For infeasible solutions at some stage, this algorithm immediately returns to the

ancestor problem to see whether a feasible solution can be generated. This alter-

native appears practical because subsequent iterations with a currently infeasible

solution do not seem worthwhile.

We note that much of this algorithm can also run in parallel. We refer to

Ruszczy´nski [1993a] who describes parallel procedures in detail. Again, one should

pay attention in parallel implementations to the possible additional work for solving

similar subproblems as we mentioned in Chapter 5. The convergence of this method

is relatively straightforward, as given in the following.

Theorem 1. If all

are ﬁnite and all x

have ﬁnite upper bounds, then the nested

L -shaped method converges ﬁnitely to an optimal solution of (3.4.1).

6.1 Nested Decomposition Procedures 269

Proof: First, we wish to demonstrate that all cuts generated by the algorithm are

valid outer linearizations of the feasible regions and objectives in (3.4.3). By induc-

tion on t , suppose that all feasible cuts (1.3) generated by the algorithm for periods

t or greater are valid. For t = H , no cuts are present so this is true for the last pe-

riod. In this case, for any

≥ 0 such that (

)

≤ 0,wemust

have (

)

−T

t−1

a(k)

)+(

)

≤ 0 to maintain feasibility. Because this is

the cut added, these cuts are valid for t −1 . Thus, the induction is proved.

Now, suppose the cuts in (1.3)-(1.4) are an outer linearization of Q

t+1

) for

t or greater and all k . In this case, for any (

) feasible in (1.1)–(1.5)for

t and k , (

)

−T

t−1

a(k)

∑

i=1

(

)

∑

i=1

(

)

is a lower bound on

a(k)

t−1

a(k)

,k) for any x

t−1

a(k)

, each k ,and a(k) . Thus, we must have

a(k)

t−1

a(k)

) ≥

∑

k∈D

(a(k))



t−1

a(k)





(

)

−T

t−1

a(k)

)

∑

i=1

(

)

∑

i=1

(

)



, (1.6)

which says that

t−1

≥−E

t−1

a(k)

t−1

a(k)

+ e

t−1

a(k)

, as found in the algorithm. Thus, again,

we achieve a valid cut on Q

t−1

a(k)

for any a(k) , completing the induction.

Now, suppose that the algorithm terminates. This can only happen if (1.1)–(1.5)

is infeasible for t = 1 or if each subproblem for t = 2 has been solved and no cuts

are generated. In the former case, the problem is infeasible, because the cuts (1.3)

are all outer linearizations of the feasible region. In the latter case, we must have

= Q

) , the condition for optimality.

For ﬁniteness, proceed by induction. Suppose that at stage t ,atmostaﬁnite

number of cuts from stage t + 1toH can be generated for each k at t .For H ,

this is again trivially true. Because at most a ﬁnite number of cuts are possible at

each k , at most a ﬁnite number of basic solutions, (

) , can be generated to

form cuts for a(k) . Thus, at most a ﬁnite number of cuts can be generated for all

a(k) at t −1 , again completing the induction.

The proof is complete by noting that every iteration of Step 1 or 2 produces a

new cut. Because there is only a ﬁnite number of possible cuts, the procedure stops

ﬁnitely.

The nested L -shaped method has many features in common with the standard

two-stage L -shaped algorithm. There are, however, peculiarities about the multi-

stage method. We consider the following example in some detail to illustrate these

features. In particular, we should note that the two-stage method always produces

cuts that are supports of the function Q if the subproblem is solved to optimality.

In the multistage case, with the sequencing protocol just given, we may not actu-

ally generate a true support so that the cut may lie strictly below the function being

approximated.

270 6 Multistage Stochastic Programs

Example 1

Suppose we are planning production of air conditioners over a three month period.

In each month, we can produce 200 air conditioners at a cost of $100 each. We

may also use overtime workers to produce additional air conditioners if demand is

heavy, but the cost is then $300 per unit. We have a one-month lead time with our

customers, so that we know that in Month 1, we should meet a demand of 100.

Orders for Months 2 and 3 are, however, random, depending heavily on relatively

unpredictable weather patterns. We assume this gives an equal likelihood in each

month of generating orders for 100 or 300 units.

We can store units from one month for delivery in a subsequent month, but we

assume a cost of $50 per unit per month for storage. We assume also that all demand

must be met. Our overall objective is to minimize the expected cost of meeting de-

mand over the next three months. (We assume that the season ends at that point and

that we have no salvage value or disposal cost for any leftover items. This resolves

the end-of-horizon problem here.)

Let x

be the regular-time production in scenario k at month t ,let y

be the

number of units stored from scenario k at month t ,let w

be the overtime pro-

duction in scenario k at month t ,andlet d

be the demand for month t under

scenario k . The multistage stochastic program in deterministic equivalent form is:

min x

+ 3.0w

+ 0.5y

∑

k=1

+ 3.0w

+ 0.5y

)

∑

k=1

+ 3.0w

)

s. t. x

≤ 2 ,

+ w

−y

= 1 ,

+ x

+ w

−y

= d

≤ 2 , k = 1,2 ,

a(k)

+ x

+ w

−y

= d

≤ 2 , k = 1,...,4 ,

≥ 0 , k = 1,...,K

, t = 1,2, 3 ,

(1.7)

where a(k)=1,if k = 1,2atperiod3,a(k)=2ifk = 3,4atperiod3,p

0.5, k = 1,2, p

= 0.25 , k = 1,...,4, d

= 1, d

= 3,and d

=(1,3, 1,3)

The nested L -shaped method applied to (1.7) follows these steps for the ﬁrst two

iterations. We list an iteration at each change of DIR .

Step 0. All subproblems NLDS(t, k) have the explicit

= 0 constraint. DIR =

FORE .

6.1 Nested Decomposition Procedures 271

Iteration 1:

Step 1.Here t = 1, k = 1 . The subproblem NLDS(1,1) is:

min x

+ 3w

+ 0.5y

s. t. x

≤ 2 ,

+ w

−y

= 1 ,

≥ 0 ,

= 0 ,

(1.8)

which has the solution x

= 1 ; other variables are zero.

Step 1.Now, t = 2, k = 1,and NLDS(2,1) is

min x

+ 3w

+ 0.5y

s. t. x

≤ 2 ,

+ w

−y

= 1 ,

≥ 0 ,

= 0 ,

(1.9)

which has the solution, x

= 1 ; other variables are zero.

Step 1. Here, t = 2, k = 2,and NLDS(2,2) is

min x

+ 3w

+ 0.5y

s. t. x

≤ 2 ,

+ w

−y

= 3 ,

≥ 0 ,

= 0 ,

(1.10)

which has the solution, x

= 2, w

= 1 ; other variables are zero.

Step 1.Next, t = 3, k = 1. NLDS(3, 1) is

min x

+ 3w

+ 0.5y

s. t. x

≤ 2 ,

+ w

−y

= 1 ,

≥ 0 ,

= 0 ,

(1.11)

272 6 Multistage Stochastic Programs

which has the solution, x

= 1 ; other primal variables are zero. The complementary

basic dual solution is

=(0,1)

Step 1.Next, t = 3, k = 2. NLDS(3,2) has the same form as

NLDS(3,1) , except we replace the second constraint with x

+ w

−y

= 3.Ithas

the solution, x

= 2, w

= 1 ; other primal variables are zero. The complementary

basic dual solution is

=(−2,3)

Step 1.For t = 3, k = 3 , we have the same subproblem and solution as t = 3,

k = 1,so x

= 1 ; other primal variables are zero. The complementary basic dual

solution is

=(0,1)

Step 1.For t = 3, k = 4 , we have the same subproblem and solution as t = 3,

k = 2, x

= 2, w

= 1 ; other primal variables are zero. The complementary basic

dual solution is

=(−2,3)

.Now, DIR = BACK , and we go to Step 2.

Iteration 2:

Step 2. For scenario j = 1andt −1 = 2,wehave



0.25

0.5



(

)

=(0.5)







000

001



+(0.5)



−23





000

001





002



(1.12)

and



0.25

0.5



(

)

=(0.5)









+(0.5)



−23







= 3 , (1.13)

which yields the constraint, 2y

≥ 3,toaddto NLDS(2,1) .

For scenario j = 2att −1 = 2 , we have the same, E



002



, e

= 3.

Now t = 2andk = 1.

Step 1. NLDS(2,1) is now:

min x

+ 3w

+ 0.5y

s. t. x

≤ 2 ,

+ w

−y

= 1 ,

≥ 3 ,

≥ 0 ,

(1.14)

6.1 Nested Decomposition Procedures 273

which has an optimal basic feasible solution, x

= 2, y

= 1,

= 1, w

= 0,

with complementary dual values,

=(−0.5,1.5)

= 1.

Step 1. NLDS(2,2) has the same form as (1.14) except that the demand constraint

is x

+ w

−y

= 3 . The optimal basic feasible solution found to this problem is

= 2, w

= 1,

= 3, y

= 0 , with complementary dual values,

=(−2, 3)

= 1 . We continue in DIR = BACK to Step 2.

Step 2. For scenario t −1 = 1,wehave

=(0.5)(

)

=(0.5)



−0.51.5





000

001



+(0.5)



−23





000

001





002.25



(1.15)

and

=(0.5)(

)+(0.5)(

)

=(0.5)



−0.51.5







+(0.5)



−23







+(0.5)((1)(3)+(1)3)

=(0.5)(0.5 + 5 + 6)=5.75, (1.16)

which yields the constraint, 2.25y

≥ 5.75 , to add to NLDS(1) .

Step 1. NLDS(1) is now:

min x

+ 3w

+ 0.5y

s. t. x

≤ 2 ,

+ w

−y

= 1 ,

2.25y

≥ 5.75 ,

≥ 0 ,

(1.17)

with optimal basis feasible solution, x

= 2, y

= 1, w

= 0,

= 3.5. DIR =

FORE .

This procedure continues through six total iterations to solve the problem. At the

last iteration, we obtain

= 3.75 =

, so no new cuts are generated for Period

1 . We stop with a current solution as optimal, x

1∗

= 2, y

1∗

= 1, z

∗

= 2.5 + 3.75 =

6.25 . In Exercise 2, we ask the reader to generate each of the cuts.

Following the nested L -shaped method completely takes many steps in this ex-

ample, six iterations or changes of direction corresponding to three forward passes

and three backward passes. Figure 1 illustrates the process and provides some in-

sight into nested decomposition performance.