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

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

194 5 Two-Stage Recourse Problems

A third case is when Step 2 is not required for all k = 1,...,K , but for one h

Assume T is deterministic. Also assume we can transform W so that for all t ≥0,

t ∈ pos W . This poses no difﬁculty for inequalities, as it is just a matter of taking

the slack variables with a positive coefﬁcient. In Example 4.2 discussed above, the

following representation of W satisﬁes the desired requirement:

+2y

+5y

−y

= −0.8d

−y

= −0.8d

For any t ≥ 0 , it sufﬁces to take w = t to have a second-stage feasible solution.

Assume ﬁrst some lower bound,

b(x) ≤ h

−T

x , k = 1,...,K ,

exists. Then a sufﬁcient condition for x to be feasible is that the linear system:

Wy= b(x) , y ≥ 0 , is feasible. Indeed, if Wy = b(x) , y ≥0 is feasible, then Wy =



(x) , y ≥ 0 is feasible for any b



(x) ≥ b(x) by construction of W .

Theorem 1. Assume that W is such that t ∈ pos W for all t ≥ 0 . Deﬁne a

min

k=1,...K

} to be the componentwise minimum of h . Also assume there exists one

realization h



, ∈{1,...,K} s.t. a = h



. Then, x ∈ K

if and only if Wy = a −

Tx, y ≥0 is feasible.

Proof: This is easily checked, as the condition was just seen to be sufﬁcient. It is

also necessary because x ∈ K

only if Wy = a −Tx, y ≥ 0 is feasible.

Again taking the same example of the previous section, we observe that, with

an appropriate choice of W , the vector h =(0,0,

,−0.8

)

.The

componentwise minimum is a =(0, 0,4,−4.8,4, −6.4)

. Unfortunately, no h co-

incides with a . The system {y |Wy = a −Tx, y ≥0} is infeasible.

On the other hand, the system is feasible only if 3y

+ 2y

≤ x

,2y

+ 5y

≤

, y

≥ 0.8

is feasible (we just drop the upper bounds on y ). This

reduced system is feasible if and only if

+ 2y

≤ x

+ 5y

≤ x

, y

≥ 4.8 , y

≥ 6.4 ,

i.e., if and only if x

≥ 27.2andx

≥ 41.6 , which (as already seen intuitively) is

a necessary condition for feasibility. Thus, even if in practice there does not always

exist a realization h



such that a = h



, the condition of Theorem 1 may still be

helpful.

5.1 The L -Shaped Method 195

Exercises

1. Consider Step 3 of Iteration 1 within Example 1.

(a) For

and x = x

, the second-stage program is

w = min{−24y

−28y

| 6y

+ 10y

≤ 2400 ,

+ 5y

≤ 1600 , 0 ≤ y

≤ 500 , 0 ≤ y

≤ 100}.

You may want to check that the optimal dictionary is

w = −6100 +3s

+13s

= 575 +6/8s

+50/8s

= 137.5−1/8s

+5/8s

= 362.5+1/8s

−5/8s

= 100 −s

where s

and s

are the slacks of the two constraints and s

and s

the

slacks of the upper bound constraints.

Check that this dictionary corresponds to the solution stated in Example 1.

Check that the optimal value w = −6100 is also obtained through the dual

variables.

(b) For

, the optimal solution is w

= −6100 and for

,the

optimal solution is w

= −8384 . Check that w

= 0.4w

+ 0.6w

Prove by linear programming duality that w =

∑

k=1

,where w

de-

notes the solution of the second-stage program for realization k of ξ ,

k = 1,...,K .

w = −8384+2.32s

+1.76s

= 192 −0.16s

+0.12s

= 80 +0.1s

−0.2s

= 220 −0.1s

+0.2s

= 108 +0.16s

−0.12s

Obtain the two optimal dictionaries if x

=(35, 25)

instead of (40,20)

Show that the cut is unchanged.

(d) Consider again x

=(40,20)

. From the two dictionaries given in (a) and

(c), construct the range of values of x where the same cut is obtained.

2. Consider the following problem:

min 7x

+ 11x

+ E

+ q

)

196 5 Two-Stage Recourse Problems

s. t. y

+ 2y

≥ d

−x

≥ d

−x

0 ≤ x

≤10 , 0 ≤x

≤ 10 , y

≥ 0,

where ξ

=(q

) takes on the values (26,16,6,12) and

(14,24,10, 4) with probability 0.5 each.

(a) In this example, the L -shaped method selects x

=(0,0)

as starting point

(Step l of Iteration 1). The L -shaped method can however be used with any

other reasonable starting point. Take x =(1, 5)

as starting point. Show

that the L -shaped then ﬁnds an optimal solution in three iterations (which

means adding only two optimality cuts).

(b) Show that exactly the same steps are taken if the starting point is any point

within the region 4 ≤ x

≤ 6 + x

bounds on the variables. Explain why the L -shaped method needs at least

two cuts to terminate, unless at least one variable is at a bound at the opti-

mum.

(d) Prove that the optimality cuts can also be constructed from the primal solu-

tions of the second stage programs.

(e) Show that the ﬁrst-stage feasibility set K

= {0 ≤ x

≤ 10 , 0 ≤ x

≤ 10}

can be partitioned in four regions, each one yielding a different optimality

cut . The regions are R

= {x ∈ K

−6 ≤x

≤4}, R

= {x ∈ K

| x

≤

−6}, R

= {x ∈ K

| 4 ≤ x

≤ 6 + x

}, R

= {x ∈ K

| x

+ 6 ≤ x

3. Consider the problem of Exercise 2. Assume the second-stage includes the re-

quirements: y

≤ 15 , y

≤ 2 . Obtain the feasibility cuts.

4. Feasibility cuts in Benders decomposition have an equivalent in Dantzig-Wolfe

decomposition. What is it?

c. Proof of convergence

We now constructively prove that constraints of the type (1.4) deﬁned in Step 3 are

supporting hyperplanes of Q(x) and that the algorithm will converge to an optimal

solution, provided the constraints (1.3) adequately deﬁne feasible points of K

.We

then prove that at most ﬁnitely many cuts (1.3) are needed to guarantee x ∈ K

First, observe that solving (3.1.3), namely,

min c

x + Q(x)

s. t. x ∈K

∩K

, (1.12)

is equivalent to solving

5.1 The L -Shaped Method 197

min c

x +

(1.13)

s. t. Q(x) ≤

, (1.14)

x ∈K

∩K

where, in both problems, Q(x) is deﬁned as in (3.1.3),

Q(x)=E

Q(x,

(

))

and

Q(x,

(

)) = min

{q(

)

y |Wy = h(

) −T(

)x,y ≥0}

as in (3.1.4).

We are thus looking for a ﬁnitely convergent algorithm for solving (1.12)or

(1.13). In Step 3 of the algorithm, problem (1.5) is solved repeatedly for each k =

1,...,K , yielding optimal simplex multipliers

, k = 1,...,K . It follows from

duality in linear programming that, for each k ,

Q(x

)=(

)

−T

) .

Moreover, by convexity of Q(x,

) , it follows from the subgradient inequality that

Q(x,

) ≥ (

)

−(

)

x .

We may now take the expectation of these two relations to obtain

Q(x

)=E(π

)

(h−Tx

∑

k=1

·(

)

−T

)

and

Q(x) ≥ E(π

)

(h−Tx)=

∑

k=1

(

)

−



∑

k=1

(

)



x ,

respectively. By

≥ Q(x) , it follows that a pair (x,

) is feasible for (1.13) only

≥ E(π

)

(h−Tx) , which corresponds to (1.4)where E



and e



are deﬁned

in (1.6)and(1.7).

On the other hand, if (x

) is optimal for (1.13), it follows that Q(x

because

is unrestricted in (1.13) except for

≥Q(x) . This happens when

E(π

)

(h−Tx

) , which justiﬁes the termination criterion in Step 3.

This means that at each iteration either

≥ Q(x

) implying termination or

< Q(x

) . In the latter case, none of the already deﬁned optimality cuts (1.4)

adequately imposes

≥Q(x) ; so, a new set of multipliers

will be deﬁned at x

to generate an appropriate constraint (1.4). The ﬁnite convergence of the algorithm

follows from the fact that there is only a ﬁnite number of different combinations

of the K multipliers

, because each corresponds to one of the ﬁnitely many

different bases of (1.5).

198 5 Two-Stage Recourse Problems

An alternative proof of convergence could be obtained by showing that Step 3 co-

incides with an iteration of the subproblems in the Dantzig-Wolfe decomposition of

the dual of (1.12) while Step 1 coincides with the master problem. We will consider

this approach in Section 5.6.

We now have to prove that at most a ﬁnite number of constraints (1.3) is needed

to guarantee x ∈ K

. Constraints (1.3) are generated in Step 2 of the algorithm. By

deﬁnition, x ∈ K

is equivalent to

x ∈{x | for k = 1,...,K , ∃y ≥0s.t. Wy = h

−T

x} .

Referring to a previously introduced notation, this means

−T

x ∈pos W , for k = 1,...,K .

In Step 2, a subproblem (1.8) is solved that tests whether h

−T

belongs to pos

W for k = 1,...,K . If not, this means that for some k = 1,...,K , h

−T

∈

pos W . Then, there must be a hyperplane separating h

−T

and pos W .This

hyperplane must satisfy

t ≤ 0forallt ∈ pos W and

−T

) > 0.In

Step 2, this hyperplane is obtained by taking

for the value

of the simplex

multipliers of the subproblem (1.8)solvedinStep2.

By duality, w



being strictly positive is the same as (

)

−T

) > 0.Also,

(

)

W ≤ 0 is satisﬁed because

is an optimal simplex multiplier and, at the

optimum, the reduced costs associated with y must be non-negative. Therefore,

has the desired property. A necessary condition for x belonging to K

is that

(

)

−T

x) ≤ 0 . There is at most a ﬁnite number of such constraints (1.3)

because there are only a ﬁnite number of optimal bases to the problem (1.8)solved

in Step 2. This is no surprise because we already know from Theorem 3.5 that K

polyhedral when ξ is a ﬁnite random variable. We thus have proved the following

theorem.

Theorem 2. When ξ is a ﬁnite random variable, the L -shaped algorithm ﬁnitely

converges to an optimal solution when it exists or proves the infeasibility of Problem

(3.1.2), namely,

min c

x + Q(x)

s. t. x ∈K

∩K

d. The multicut version

In Step 3 of the L -shaped method, all K realizations of the second-stage program

are optimized to obtain their optimal simplex multipliers. These multipliers are then

aggregated in (1.10)and(1.11) to generate one cut (1.4). The structure of stochastic

5.1 The L -Shaped Method 199

programs clearly allows placing several cuts instead of one. In the multicut version,

one cut per realization in the second stage is placed. For those familiar with Dantzig-

Wolfe decomposition (explored more deeply in Section 5.5), adding multiple cuts

at each iteration corresponds to including several columns in the master program of

an inner linearization algorithm (see, e.g., Lasdon [1970] for a general presentation

and Birge [1985b] for an analysis of the stochastic case). We ﬁrst give a presentation

of the multicut algorithm, taken from Birge and Louveaux [1988].

The Multicut L -Shaped Algorithm

Step 0.Set r =

= 0ands

= 0forallk = 1,...,K .

Step 1.Set

+ 1 . Solve the linear program (1.15)–(1.18):

min z = c

∑

k=1

(1.15)

s. t. Ax =b , (1.16)



x ≥d



,= 1,...,r , (1.17)

(k)

x +

≥e

(k)

,(k)=1,...,s

, (1.18)

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

Let (x

,...,

) be an optimal solution of (1.15)–(1.18). If no constraint (1.18)

is present for some k ,

is set equal to −∞ and is not considered in the compu-

tation of x

Step 2. As before.

Step 3.For k = 1,...,K solve the linear program (1.9). Let

be the simplex

multipliers associated with the optimal solution of problem k .If

< p

(

)

−T

) , (1.19)

deﬁne

= p

(

)

, (1.20)

= p

(

)

, (1.21)

and set s

= s

+ 1.If (1.19) does not hold for any k = 1,...,K , stop; x

is an

optimal solution. Otherwise, return to Step 1.

We illustrate the multicut L -shaped method on Example 2. Starting from x

= 0,

the sequence of iterations is as follows:

Iteration 1:

is not optimal, add the cuts

200 5 Two-Stage Recourse Problems

≥

1 −x

;

≥

2 −x

;

≥

4 −x

Iteration 2:

= 10 ,

= −3,

= −8/3,

= −2 is not optimal; add the cuts

≥

x −1

;

≥

x −2

;

≥

x −4

Iteration 3:

= 2,

= 1/3,

= 0,

= 2/3 is the optimal solution.

Let us deﬁne a major iteration to consist of the operations performed between re-

turns to Step 1 in both algorithms. By adding multiple cuts, a solution is found in

two major iterations instead of four with the single-cut L -shaped method.

A few observations are necessary. By adding disaggregate cuts, more detailed

information is given to the ﬁrst stage. The number of major iterations is expected

then to be fewer than in the single cut method. Because the two methods do not

necessarily follow the same path, by chance, the L -shaped method can conceivably

do better than the multicut approach. Exercise 1 provides such an example.

In general, however, as numerical experiments reveal, the number of major itera-

tions is reduced. This is done at the expense of a larger ﬁrst-stage program, because

many more cuts are added. The balance between fewer major iterations but larger

ﬁrst-stage programs is problem-dependent. The results of numerical experiments

are available in Birge and Louveaux [1988] and Gassmann [1990]. As a rule of

thumb, the multicut approach is expected to be more effective when the number of

realizations K is not signiﬁcantly larger than the number of ﬁrst-stage constraints

Finally, some hybrid approach may be worthwhile, where subsets of the realiza-

tions are grouped to form a smaller number of combination cuts. Exercise 2 provides

such an example.

Exercises

5. Assume n

= 1, m

= 0, m

= 3, n

= 6,

W =

⎛

⎝

1 −1 −1 −100

010010

001001

⎞

⎠

and K = 2 realizations of ξ with equal probability 1/2 . These realizations

are

=(q

)

and

=(q

)

,where q

=(1,0,0,0, 0,0)

5.1 The L -Shaped Method 201

=(3/2,0, 2/7,1,0,0)

, h

=(−1, 2,7)

, h

=(0, 2,7)

,and T

= T

(1,0, 0)

. For the ﬁrst value of

, Q(x,

) has two pieces, such that

(x)=



−x −1ifx ≤−1,

0ifx ≥−1 .

For the second value of

, Q(x,

) has four pieces such that

(x)=

⎧

⎪

⎨

⎪

⎩

−1.5x if x ≤0 ,

0if0≤ x ≤ 2,

2/7(x −2) if 2 ≤x ≤ 9 ,

x −7ifx ≥ 9 .

Assume also that x is bounded by −20 ≤x ≤20 and c = 0 . Starting from any

initial point x

≤−1 , show that one obtains the following sequence of iterate

points and cuts for the L -shaped method.

Iteration 1:

= −2,

is omitted; new cut:

≥−0.5 −1.25x .

Iteration 2:

=+20 ,

= −25.5 ; new cut:

≥ 0.5x −3.5.

Iteration 3:

= 12/7,

= −37/14 ; new cut:

≥ 0.

Iteration 4:

∈ [−2/5,7] ,

= 0. If x

is chosen to be any value in [0,2] , then the

algorithm terminates at Iteration 4. The multicut approach would generate the

following sequence.

Iteration 1:

= −2,

and

omitted; new cuts:

≥−0.5x −0.5,

≥−3/4x .

Iteration 2:

= 20 ,

= −10.5,

= −15 ; new cuts:

≥ 0,

≥ 0.5x −3.5.

Iteration 3:

= 2.8,

= 0,

= −2.1 ; new cut:

≥ 1/7(x −2) .

Iteration 4:

= 0.32 ,

= 0,

= −0.24 ; new cut:

≥ 0.

202 5 Two-Stage Recourse Problems

Iteration 5:

= 0,

= 0 , stop.

6. Consider Example 2, now with ξ taking values:

0.5,1.0,1.5 with probability 1/9 each,

2 with probability 1/3 ,

3,4, 5 with probability 1/9 each.

As can be seen, the expectation of ξ is still 2

, and new uncertainty is added

around 1 and 4 .

(a) Show that the L -shaped method follows exactly the same path as before

( x

= 0, x

= 10 , x

= 7/3, x

= 1.5, x

= 2 ) provided that in Itera-

tion 4, the support is chosen to describe the region [1.5,2] . If it is chosen

to describe the region [1, 1.5] , one more iteration is needed.

(b) Show the multicut version also follows the same path as before ( x

= 0,

= 10 , x

= 2).

(x)+Q

(x)] ,where Q

(x) is the expectation over the three

realizations 0.5, 1.0, and 1.5 (conditional on ξ being in the group

{0.5,1.0,1.5}), Q

(x)=Q(x,

= 2) ,and Q

(x) is the (similarly con-

ditional) expectation over the realizations 3 , 4 , and 5 . Thus, the objective

becomes

(

) . Show that in Iteration 1, the cuts at x

= 0are

≥ 1 −x ,

≥ 2 −x ,and

≥ 4 −x . In Iteration 2, x

= 10 , and the

cuts become

≥x −1,

≥x −2,and

≥x −4 . Show, without com-

putations, that only two major iterations are needed. What conclusions can

you draw from this example?

5.2 Regularized Decomposition

Regularized decomposition is a method that combines a multicut approach for the

representation of the second-stage value function with the inclusion in the objec-

tive of a quadratic regularizing term. This additional term is included to avoid two

classical drawbacks of the cutting plane methods. One is that initial iterations are

often inefﬁcient. The other is that iterations may become degenerate at the end of

the process. Regularized decomposition was introduced by Ruszczy´nski [1986].

We present a somewhat simpliﬁed version of his algorithm using the notation of

Section 5.1d.

5.2 Regularized Decomposition 203

The Regularized Decomposition Method

Step 0.Set r =

= 0, s

= 0forallk = 1,...,K . Select a

, a feasible solution.

Step 1.Set

+ 1 . Solve the regularized master program

min c

x +

∑

k=1

x −a



(2.1)

s. t. Ax = b ,



x ≥d



,= 1,...,r ,

(k)

x +

≥ e

(k)

,(k)=1,...,s

, k = 1,...,K ,

x ≥0 .

Let (x

) be an optimal solution to (2.1)where (

)

,...,

)

is the

vector of

’s. If s

= 0forsomek ,

is ignored in the computation. If c

= c

+ Q(a

) , stop; a

is optimal.

Step 2. As before, if a feasibility cut (5.1.3) is generated, set a

= a

(null infea-

sible step), and go to Step 1.

Step 3.For k = 1,...,K , solve the linear subproblem (5.1.9). Compute Q

) .If

(5.1.19) holds, add an optimality cut (5.1.18) using formulas (5.1.20)and(5.1.21).

Set s

= s

+ 1.

Step 4.If(5.1.19) does not hold for any k ,then a

= x

(exact serious step); go

to Step 1.

Step 5.If c

+ Q(x

) ≤ c

+ Q(a

) ,then a

= x

(approximate serious

step); go to Step 1. Else, a

= a

(null feasible step), go to

Step 1.

Observe that when a serious step is made, the value Q(a

) should be memo-

rized, so that no extra computation is needed in Step 1 for the test of optimality. Note

also that a more general regularization would use a term of the form

x −a



with

> 0 . This would allow tuning of the regularization with the other terms in

the objective. As will be illustrated in Exercise 2, regularized decomposition works

better when a reasonable starting point is chosen.

Example 1 (continued)

Consider Exercise 1 of Section 5.1d. Take a

= −0.5 as a starting point. It cor-

responds to the solution of the problems with

with probability 1. We have

Q(a

)=3/8.

Iteration 1: Cuts

≥ 0,

≥−

x are added. Let a

= a