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

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

284 6 Multistage Stochastic Programs

s. t. w

−h

+ f

= 50 ,

, f

≥ 0 .

Its optimal solution, w

= 60 , h

= 10 , belongs to C

and is thus also the optimal

solution of the global problem with objective value −292.5.

Many two-stage methods may also be enhanced for multiple stages using some

form of block separability. One such approach assumes deviations from some mean

value can be corrected by a penalty only relating to the current period. This method

basically applies a simple recourse strategy in every period. For example, in Kall-

berg, White and Ziemba [1982] and Kusy and Ziemba [1986], penalties are imposed

to meet ﬁnancial requirements in each period of a short-term ﬁnancial planning

model. With this type of penalty, the various simple recourse methods may be ap-

plied to achieve efﬁcient computation.

Exercises

1. Does the block separable property depend on having a single product? To help

answer this question, take the example in the block separability paragraph and

assume a second product with revenue 0.6 in normal time and 0.3 in overtime.

One worker produces 10 such products in one stage. Obtain Q

t+1

) ,

(a) if demand in Period t is known to be 400 ;

(b) if demand in Period t is uniform continuous within [0,500] and [0,100] ,

respectively, for the two periods.

2. In the case of one product, obtain Q

t+1

) if demand follows a negative ex-

ponential distribution with known parameter

. Based on Louveaux [1978],

extend the MQSP to the piecewise convex case, then solve the problem with

= 0.01 and 0.02 for the two periods.

6.4 Lagrangian-Based Methods for Multiple Stages

The general goal in Lagrangian methods as in Section 5.8 is to relax a difﬁcult

constraint and place it in the objective to obtain a more efﬁcient subproblem to solve.

In stochastic programming, candidate constraints to relax include those that enforce

nonanticipativity when the formulation imposes this restriction explicitly as in the

progressive hedging algorithm (PHA). PHA is easily adapted for multiple stages

by simply deﬁning the projection,

, to project onto the space of nonanticipative

solutions by deﬁning it as the conditional expectation of all solutions at time t that

correspond to the same history up to t .

6.4 Lagrangian-Based Methods for Multiple Stages 285

The main subproblem for the H -period case is a direct extension of (5.8.10)as

follows.

infz =

∑

k=1

[ f

∑

t=1

t+1

,k)+

− ˆx

)+r/2x

− ˆx



]

s. t. g

) ≤ 0 , i = 1,...,m

, k = 1,...,K ,

t+1

,k) ≤ 0 , i = 1,...,m

;t = 1,...,H , k = 1,...,K ,

(4.1)

where x

represents given initial conditions.

This formulation leads then to the PHA for multistage problems.

Multistage Progressive Hedging Algorithm

Step 0. Suppose some nonanticipative x

=(x

,k = 1,...,K;t = 1,...,H) ,ˆx

= x

initial multiplier

,and r > 0.Let

= 0.GotoStep1.

Step 1.Let (x

) for k = 1,...,K solve (4.1). Let ˆx

) ,sothat

ˆx

(i)=ˆx



(i) in all components i corresponding to decisions x

at time t

whenever k and k



share the same history until time t .

Step 2.Let

+ r(x

+1,k

− ˆx

) .If ˆx

= ˆx

and

, then,

stop; ˆx

and

are optimal. Otherwise, let

+ 1 and go to Step 1.

To see how the algorithm applies to multiple stages, consider an extended version

of Example 3 in Chapter 5. Suppose a three-stage example with the same returns on

investments A and B in each period as in that example, with a goal of achieving

$55,000 at the start of the third period, and quadratic penalty for missing the goal

as before. Suppose the initial solution corresponds to equal investments in the two

assets without re-balancing after the ﬁrst period. With four future scenarios possible,

that yields x

=(x

)=((5, 5),(5,5),(5,5),(5,5), (5,10),

(5,10),(20, 15),(20,15)) . The ﬁrst steps appear below.

Iteration 0:

Step 0. Begin with a multiplier vector of

= 0 , and let ˆx

=((5,5),(5,5),(5,10),

(20,15)) .Let r = 1.

Step 1.Wewishtosolve:

min(1/2)[

∑

k=1

+(x

−5)

+(x

−5)

+(x

−5(1 + 3 ·1

k=3,4

))

−5(2 + 1

k=3,4

))

] (4.2)

286 6 Multistage Stochastic Programs

s. t. x

+ x

≤ 10 ,k = 1,...,4;

(1 + 3 ·1

k=3,4

+(2 + 1

k=3,4

))x

−x

= 0 ,k = 1,...,4;

(1 + 3 ·1

k=2,4

+(2 + 1

k=2,4

−y

≥ 55 ,k = 1,...,4;

≥ 0 ,k = 1,...,4,

(4.3)

where 1

k=X

has value 1 when k is in X and is 0 otherwise.

As in the two-stage case, this problem again separates into subproblems for each

scenario k . The solution in this case is

=((0,10),(3.91, 6.09),(6.25, 3.75),(5, 5),(0, 20),

(5.94,10.16),(19.6, 16.7),(20,15)),

which then yields

ˆx

=((3.79,6.23),(3.79,6.23),(3.79,6.23),(3.79,6.23),

(2.97,15.08),(2.97, 15.08),(19.8,15.8),(19.8,15.8)).

Step 2.Wethenhave

= 0 + 1(x

− ˆx

)

=((−3.79,3.79),(0.12,−0.12), (2.46,−2.46),(1.21,−1.21),

(−2.97,4.92), (2.97,−4.92),(−0.21,0.83),(0.21,−0.83)),

(where we use the same groupings of variables to show the relationship to x

)and

return for the next iteration. Exercise 1 asks you to complete the iterations until

convergence to within 0.01 in each component of the iterates.

As discussed in Chapter 5, PHA is particularly well-adapted for problems, such

as networks, where maintaining the original problem structure in each scenario

problem leads to efﬁciency (see Mulvey and Vladimirou [1991b]). Although PHA is

not necessarily convergent for stochastic integer problems, it and other Lagrangian

methods can be used to solve the convex relaxation with additional branching to ob-

tain integer solutions. This approach has been effective for unit commitment prob-

lems for planning electric power generation (see Takriti and Birge [2000a]). The

structure in these problems also allows for close approximations of the integer pro-

gram with the continuous-relaxation solution for large-scale problems with many

resources (see Takriti and Birge [2000b]).

A different approach for multistage problems that performs well for nonlin-

ear problems is a method from Mulvey and Ruszczy´nski [1995] called diagonal

quadratic approximation (DQA). This method approximates quadratic penalty terms

in a Lagrangian type of objective so that each subproblem is again easy to solve and

can be spread across a wide array of distributed processors. DQA requires few as-

sumptions on the problem structure and can be competitive also for linear problems.

6.4 Lagrangian-Based Methods for Multiple Stages 287

Exercises

1. Complete the PHA iterations for the three-period version of Example 5.3 until

convergence within 0.01 in every component of ˆx

and

2. Show how to implement PHA on Example 1. Follow three iterations of the

algorithm.

Chapter 7

Stochastic Integer Programs

As seen in Section 3.3, properties of stochastic integer programs are scarce. The

absence of general efﬁcient methods reﬂects this difﬁculty. Several techniques have

been proposed in the recent years. As in deterministic integer programs, many of

them are based on either a branching scheme or a reformulation scheme. The reader

unfamiliar with either concept will ﬁnd a brief introduction in the Short Reviews,

Section 7.8 of this chapter. Section 7.1 recalls the links with the continuous case.

Sections 7.2 and 7.3 consider two solution procedures that use a branching scheme.

Section 7.4 considers the use of reformulation of the second-stage constraints by

disjunctive cuts. Sections 7.5 to 7.7 consider simple integer recourse, feasibility cuts

and the decomposition of the extensive form. Approximations can also be used, as

indicated at the end of Section 9.5. Note also that Sections 7.2 to 7.7 can be read

independently of each other.

7.1 Stochastic Integer Programs and LP-Relaxation

Consider the deﬁnition of a stochastic integer program, as in Section 3.3,

(SIP) min

x∈X

x + E

min

{q(

)

y |W(

)y = h(

) −T(

)x , y ∈Y}

s. t. Ax = b , (1.1)

where the deﬁnitions of c , b , ξ , A , W , T , q and h are as before.

In this chapter, Y always contains integrality restrictions on y . In some cases,

X also contains integrality restrictions on x . The second-stage program is

Q(x,ξ)=min

{q(

)

y |W(

)y = h(

) −T(

)x , y ∈Y} , (1.2)

and its expectation Q(x)=E

Q(x,ξ) can be used to obtain a deterministic equiv-

alent program

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

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

 Springer Science+Business Media, LLC 2011

290 7 Stochastic Integer Programs

(DEP) min

x∈X

x + Q(x)

s. t. Ax = b .

Even if it does look very similar to the deterministic equivalent program in the

continuous case, we know from Section 3.3 that Q(x) does not possess appropriate

properties for an easy solution procedure. Moreover, the computation of Q(x) for a

given x is usually a much more difﬁcult task than in the continuous case. In the case

of a discrete random variable, assuming the solution of (1.2) has been obtained for

one realization of ξ does not help solving the same program for another value of

ξ . Indeed, the integrality restrictions imply that the usual forms of duality are lost.

In the continuous case, a few dual iterations generally sufﬁce to ﬁnd the solution of

(1.2) from one ξ to the other. In the integer case, (1.2) must typically be restarted

from scratch for each ξ . Thus, ﬁnding Q(x) for a given x may be a challenge in

itself. Yet, this evaluation is unavoidable (at least a few times) and the assumption

is made that, for ﬁxed x , Q(x) is computable in a ﬁnite number of steps.

Now, let

Y be the continuous or LP-relaxation of Y . For instance, if one con-

siders a stochastic program with a binary second-stage, then Y = {y |y ∈{0,1}

}

and

Y = {y | 0 ≤y ≤e} ,where e

=(1,...,1) is the unit vector of dimension m

Similarly, let

X be the LP- relaxation of X . We introduce the following notation

for the LP-relaxation of the second-stage program

C(x, ξ)=min

{q(

)

y |W(

)y = h(

) −T(

)x , y ∈Y} , (1.3)

with

C(x)=E

C(x, ξ) . (1.4)

with the usual conventions for infeasible and unbounded cases.

Proposition 1. L -shaped optimality cuts of the form (5.1.4) calculated on the con-

tinuous relaxation (1.3)–(1.4) are valid cuts for (SIP).

Proof: By deﬁnition of

Y , C(x,ξ) ≤ Q(x,ξ) holds for all x and ξ , where this

result also holds if some problem is unbounded or infeasible. Taking expectations

implies C(x) ≤ Q(x) . Following the proof in Section 5.1,an L -Shaped optimality

cut calculated on (1.3)–(1.4) is an expression of the form E

(

(h −Tx)) = e

−

x ≤ C(x) ,where

represent the optimal simplex multipliers for the second-

stage programs at iteration

,i.e.forsome x = x

. The result then follows from

−E

x ≤C(x) ≤ Q(x) ≤

Based on this observation, solving (SIP) usually starts from solving its LP-

relaxation (the program where X is replaced by

X and Y by Y ). This can typically

be done by way of the L - Shaped method and results in a program of the form

(CP) min c

x +

(1.5)

s. t. Ax = b , (1.6)

x ≥d

, l = 1,...,r , (1.7)

7.2 First-stage Binary Variables 291

x +

≥ e

, l = 1,...,s , (1.8)

x ≥ 0 ,

∈ ℜ . (1.9)

where (CP) stands for “Current Problem.”

Branching schemes typically consist of solving a sequence of (CP), each one

being deﬁned on a different subspace of the ﬁrst-stage feasibility set. Finiteness of

the procedure comes from the ﬁnite number of possible subspaces that are created.

Reformulation means that optimality cuts in (CP) are reformulated to take integrality

restrictions in the second-stage into account. Finiteness of the procedure comes from

the limited number of possible reformulations, combined or not with a second-stage

branching scheme.

7.2 First-stage Binary Variables

When the ﬁrst-stage variables are binary variables, it is possible to derive speciﬁc

optimality cuts in order to obtain a ﬁnitely convergent algorithm based on a branch-

ing system. The proposed method easily extends to the case of mixed ﬁrst-stage

variables, provided the tender variables are binary. We assume the existence of a

lower bound on Q(x) .

Assumption 2. There exists a ﬁnite lower bound L satisfying

L ≤min

{Q(x) | Ax = b , x ∈ X}.

In Assumption 2, no requirement is made that the bound L should be tight,

although it is desirable to have L as large as possible. Examples of how to ﬁnd L

will be given later.

Proposition 3. Let x

= 1 ,i∈S , and x

= 0 ,i∈S be some ﬁrst-stage feasible so-

lution. Let q

= Q(x) be the corresponding recourse function value. The optimality

cut

≥ (q

−L)



∑

i∈S

−

∑

i∈S



−(q

−L)(|S|−1)+L (2.1)

is valid.

Proof:Deﬁne

(x,S)=

∑

i∈S

−

∑

i∈S

. (2.2)

Now,

(x,S) is always less than or equal to |S|. It is equal to |S| only if x

= 1,

i ∈ S ,and x

= 0, i ∈ S . In that case, the right-hand side of (2.1) takes the value

and the constraint

≥ q

is valid as Q(x)=q

. In all other cases,

(x,S) is

smaller than or equal to |S|−1 , which implies that the right-hand side of (2.1) takes

292 7 Stochastic Integer Programs

a value smaller than or equal to L , which by Assumption 2 is a valid lower bound

on Q(x) for all feasible x .

Readers more familiar with geometrical representations may see (2.1)asahalf-

space, in the (

) space, situated above a line going through the two points

(|S|,q

) and (|S|−1, L) .

Example 1

Consider a two-stage program, where the second stage is given by

min −2y

−3y

s. t. y

+ 2y

≤ ξ

−x

≤ ξ

−x

y ≥ 0 , integer.

Assume ξ =(2,2)

or (4,3)

with equal probability 1/2 each. Find a lower

bound L on Q(x) and derive a cut of type (2.1) if the current iterate point is

x =(0,1)

1. The second stage is equivalent to: −max 2y

+ 3y

. Because the ﬁrst-stage de-

cisions are binary, largest values of y are obtained with x =(0,0)

. To obtain

a lower bound L , we simply drop the requirement that y should be integer and

solve

min −2y

−3y

s. t. y

+ 2y

≤

≥ 0 .

For

=(2,2)

, the solution is y =(2,0)

and Q(x,

)=−4 , while for

(4,3)

, the solution is y =(3, 0.5)

with Q(x,

)=−7.5 . This results in L =

0.5 ∗(−4)+0.5 ∗(−7.5)=−5.75 . (Alternatively, in this simple example, we

may have maintained the requirement that y is integer and obtained the better

bound L = −5.5 . In general, this approach seems more difﬁcult to implement.

We continue here with L = −5.75 .)

2. Here,

(x,S)=x

−x

because x

= 0andx

= 1. For

=(2,2)

,the

second stage becomes

min −2y

−3y

s. t. y

+ 2y

≤ 2 ,

≤ 1 ,

≥ 0 , integer,

7.2 First-stage Binary Variables 293

with solution y =(0,1)

and Q(x,

)=−3.For

=(4,3)

, the second stage

becomes

min −2y

−3y

s. t. y

+ 2y

≤ 4 ,

≤ 2 ,

≥ 0 , integer,

with solution y =(2,1)

and Q(x,

)=−7 . We conclude that q

= −5and

that the optimality cut (3.1) reads

≥ 0.75(x

−x

) −5.75 .

The integer L -shaped method was ﬁrst proposed by Laporte and Louveaux

[1993]. We now present a simpliﬁed version for the case of relatively complete

recourse. If needed, feasibility cuts may be added at Step 3, using the methods of

Section 7.6 for example.

Integer L -shaped Method

Step 0.Set s =

= 0, ¯z = ∞ .Thevalueof

is set to −∞ or to an appropriate

lower bound and is ignored in the computation. A list is created that contains only a

single pendant node corresponding to the initial subproblem.

Step 1.Set

+ 1 . Select some pendant node in the list as the current problem;

if none exists, stop.

Step 2. Solve the current problem. If the current problem has no feasible solution,

fathom the current node; go to Step 1. Otherwise, let (x

) be an optimal solu-

tion.

Step 3.If c

> ¯z , fathom the current problem and go to Step 1.

Step 4. Check for integrality restrictions. If a restriction is violated, create two new

branches following the usual branch and cut procedure. Append the new nodes to

the list of pendant nodes, and go to Step 1.

Step 5. Compute Q(x

) and z

= c

+ Q(x

) .If z

< ¯z , update ¯z = z

Step 6.If

≥ Q(x

) , then fathom the current node and return to Step 1. Other-

wise, impose one optimality cut (2.1) with q

= Q(x

) ,set s = s + 1 , and return

to Step 2.

Proposition 4. Under Assumption 2, the integer L -shaped method yields an op-

timal solution of a (SIP) with relatively complete recourse and ﬁrst-stage binary

variables (when one exists) in a ﬁnite number of steps.