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

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

304 7 Stochastic Integer Programs

01234567

Fig. 1 Value of the second-stage solution in Example 3 in the x -space.

(

)=min 5y

+ 3y

s. t. 2y

+ 3y

≥−3 +

+ y

≥−2.4 +

≥0 , integer,

with

= x

+ 2x

and

= x

+ x

The corresponding regions become R

= {

≤ 3 ,

≤ 2.4}, R

= {x |

≤ 6 ,

≤ 3.4}\R

, R

= {

≤ 5 ,

≤ 6.4}\R

, R

= {x |

≤

9 ,

≤ 4.4}\R

and R

= {

≤ 8 ,

≤ 7.4}\R

Figure 2 shows the regions in the

space, each region being identiﬁed by the value

(·) . Here, R

and R

are nonconvex. But now, all regions have orthogonal

boundaries.

0369

Fig. 2 Value of the second-stage solution in Example 3 in the space of tenders.

To obtain orthogonal boundaries and convex regions, the branching on tenders

method constructs hypercubes of the form H =

∏

j= 1

] .Here l

is either a

7.3 Second-stage Integer Variables 305

point of discontinuity of

(·) as a function of

or a lower bound on

. Simi-

larly, u

is either a point of discontinuity of

(·) as a function of

or an upper

bound on

In Example 3 with m

= 2 , hypercubes are rectangles. For instance, (0,6] ×

(2.4,6.4] is a hypercube since

(

) has a discontinuity point at

= 6,at

2.4andat

= 6.4 . Note that this hypercube contains several other discontinuity

points of

(

) .Thesmallest hypercubes are those where, for all j , l

and

are successive discontinuity points. One such hypercube is (3,5]×(2.4,3.4] for

example. The hypercubes based on discontinuity points of

(

) lead themselves

to easy intersections for different realizations of ξ and are also a good way to

exploit the property of

(

) being nondecreasing as a function of one particular

component

b. Discontinuity points

Let

(

) denote

(

) as a function of the j -th component of

, j =

1,...,m

Proposition 8. For any k = 1,...,K and j = 1,...,m

(

) is lower semi-

continuous and nondecreasing in

. For any a ∈ Z,

(

) is constant over

(a −h

−1,a −h

] , for any k = 1,...,K and j = 1,...,m

where h

denotes

the j -th component of h

Proof: The ﬁrst part of the proposition comes from Proposition 3.20. Now, consider

the j -th constraint (W

≥ h

.As W

is integral, it implies (W

≥

h

. Thus

(

) is constant for all

s.t. h

= h

.Taking

a = h

 provides the desired result.

Consider now

(

)=E

(

) and, as above, let

(

) denote

(

) as a

function of the j -th component of

, j = 1,...,m

Proposition 9. There exists a ﬁnite number S ≥1 of distinct values f

,s= 1,...,S

s.t. for any a ∈ Z,

(

) is constant over (a + f

,a + f

s+1

] ,s= 1,...,S,where

S+1

= f

+ 1 .

Proof: Consider a given j .Forany a ∈ Z ,

(

) is constant over (a −h

−

1,a −h

] ,forany k = 1,...,K .Let f

= a −h

−(a −h

) be the fractional

part of a −h

.Let S be the number of different such fractional parts. Clearly

1 ≤S ≤ K . Reordering the f

’s in increased order yields the desired result.

Thus, all discontinuity points of

(

) are of the form a + f

, s

= 1,...,S

a ∈Z . A special case is S

= 1 when, for instance, h

only takes on integer values.

306 7 Stochastic Integer Programs

Example 3 (continued)

Assume h take the values (−3,−2.4)

, (−3.8,−2.5)

and (−2.6,−4.4)

with

equal probability 1/3.For j = 1 , the fractional values in increasing order are 0 ,

0.6and0.8.Forany a ∈ Z , successive discontinuity points exist at a , a + 0.6,

a + 0.8, a + 1 , and so on. For j = 2 , the fractional values in increasing order are

0.4and0.5 and successive discontinuity points are of the form a + 0.4, a + 0.5,

a + 1.4 and so on, for a ∈Z .

Now consider some particular discontinuity point of

(

) ,say l

(

) is

constant over (l



] where l



is the next discontinuity point. To know

(

) over

this interval, it sufﬁces to calculate

) for some

. The chosen

must be

large enough to avoid numerical problems but smaller than l



−l

. The smallest

interval where

(

) is constant for any j is min{f

− f

, s

= 1,...,S

, j =

1,...,m

}. Thus

can be any nonzero value strictly smaller than this minimum

(for instance half the minimum). In Example 3, the smallest interval is 0.1 between

a + 0.4anda + 0.5 (for s

= 1 ). Thus

= 0.05 does the job.

c. Algorithm

Current problem

Consider a hypercube H =

∏

j= 1

] , where for each j , l

is a point of discon-

tinuity of

(

) as a function of

. Deﬁne the current problem as

CP(l,u)=min c

x +

(3.5)

s. t. x ∈X ,

= −Tx , l ≤

≤ u ,

≥

(l +

e) .

CP(l,u) is a lower bound on min

x +

(

) | x ∈ X ,

= −Tx , l ≤

≤

u}. Indeed,

(

(l +

e) for all l ≤

≤ u ,if

(·) has no discontinuity

points within H .And

(

) ≥

(l +

e) otherwise (with the inequality being

strict if

is larger than at least one discontinuity point of

(·) within H ,forat

least one j ).

The CP(l,u) problem can be strengthened by any lower bounding functionals,

such as the Bender’s cuts. We now present the branching on tenders algorithm,

assuming relatively complete recourse. If needed, feasibility cuts may be added at

Step 3, using the technique of Section 7.6.

7.3 Second-stage Integer Variables 307

Branching on Tenders Algorithm

Step 0.Set

= 0and¯z = ∞ .Set (l,u] to any relevant values s.t. {

| l <

≤

u}⊃{

| x ∈ X ,

= −Tx}. A list is created that contains the single hypercube

∏

j= 1

] , with a dummy lower bound. There is no incumbent solution.

Step 1.Set

+ 1 . Select one hypercube in the list (one with the smallest lower

bound for example). Remove it from the list. Denote it H

∏

j= 1

] . If none

exists, stop: the incumbent solution is the optimal solution.

Step 2. Solve the current problem CP(l

) . If it has no feasible solution, go to

Step 1.

Step 3.Let x

be a solution to CP(l

) . Calculate z

= z(x

) .

Step 4. (Update and fathom) If z

< ¯z , update ¯z = z

,let (x

) be the incumbent

solution and remove from the list all the hypercubes having a lower bound larger

than ¯z .

Step 5. (Fathom or Branch) If CP(l

) ≥ ¯z , go to Step 1. Find some component

j having a discontinuity point of

(·) ,say

, within (l

). If none exists, go

to Step 1. Otherwise, partition H

in two hypercubes, one having interval (l

]

in the j -th component, the other having interval (

] in the j -th component

(with the intervals for the other components unchanged). Insert the two hypercubes

in the list with a lower bound of CP(l

) each. Go to Step 1.

Proposition 10. The branching on tenders algorithm terminates with a global min-

imum (when one exits) in a ﬁnite number of steps.

Proof: Assume X contains at least one solution. Partitioning (or branching) occurs

at Step 5. This operation is ﬁnite if X is compact. Indeed, there can only be a ﬁnite

number of discontinuity points for each component, thus a ﬁnite number of parti-

tions. At each iteration, at least one hypercube is fathomed. Thus, there can only

be a ﬁnite number of iterations. Now, consider an optimal solution, say x

∗

with

objective value z

∗

and let H

∗

be the smallest hypercube containing

∗

.Thisisa

hypercube such that

(·) does not contain any discontinuity. Thus,

(·) is con-

stant on H

∗

and the solution of the LB problem on H

∗

must be

∗

(or another

with equal z

∗

value). Otherwise there would be another

within H

∗

with strictly

smaller c

x +

(

) value, contradicting the optimality of

∗

. Within the list of

hypercubes, there will always be one hypercube containing H

∗

, unless the optimum

is found at step 4, in which case the proposition holds. Along the iterations, the hy-

percube containing H

∗

will be partitioned (at most a ﬁnite number of times) up to

the point where H

∗

enters the list. When H

∗

is selected in Step 1, the optimum is

found in Step 4.

308 7 Stochastic Integer Programs

Example 4

Consider the following stochastic integer program

min

x≥0

−2.5x

−2x

+ E

min{4.4y

+ 3y

}

s. t. 4x

+ 5x

≤ 15 , 2y

+ 3y

≥ h

+ x

≥ 1.5 , 4y

+ y

≥ h

= x

+ 2x

, y ≥ 0 , integer,

= 2x

+ x

where h

=(−2.8,−1.2) and (−2, −3) with equal probability

We use the following notation. The list of remaining hypercubes is denoted by

. An upper index on a hypercube represents the iteration number, while a lower

index represents its place in the list.

represents the lower bound associated to a

particular hypercube. Thus,

= hypercube selected at iteration

;

= i-th hypercube in the list, with lower bound

Given the possible values of h ,

can take any value 0 <

< 0.2 . We choose

= 0.1 . We use the ﬁrst-stage feasibility set to ﬁnd the feasibility intervals 1.5 ≤

≤ 6, 1.5 ≤

≤ 7.5 . As the left intervals of hypercubes are open, we subtract

on the left part to make sure no feasible point is omitted. The initial hypercube is

=(1.4,6] ×(1.4, 7.5] .Set ¯z = 0and

= 0.

Iteration 1:

Step 1.

= 1 . Select H

= H

is empty.

Step 2. l

=(1.4, 1.4)

and u

=(6,7.5)

Compute

e)=

(1.5,1.5) :for h =(−2.8, −1.2)

, the second-stage so-

lution is y =(0,1)

and

(

)=3,for h =(−2,−3)

,itis y =(0,0)

with

(

)=0 . Taking the expectation, we obtain

(1.5,1.5)=1.5 . The current

problem reads as follows:

CP(l

)=min −2.5x

−2x

s. t. 4x

+ 5x

≤ 15 , x

+ x

≥ 1.5 ,

= x

+ 2x

= 2x

+ x

1.5 ≤

≤ 6 , 1.5 ≤

≤ 7.5 , x

≥ 0 ,

≥ 1.5 ,

≥−4.62 + 2.2

≥−2.32 + 0.5

+ 1.1

≥−2.64 + 0.7

+ 0.9 .

7.3 Second-stage Integer Variables 309

The last three constraints are Benders’ cuts expressed in terms of

and

.The

reader may check that the solution of the current problem with these three cuts is also

the solution of the continuous LP-relaxation of the problem. The current problems

in the next iterations only differ by the bounds on

and the corresponding

≥

e) bound. Some of the current problems have multiple solutions.A different

selection than ours would alter the course of the iterations.

Step 3. The solution of the current problem is x

=(0.096,1.696)

=(3.488,

1.887)

and CP(l

)=−2.131 . Compute the value of

(

(3.8,2) .For

h =(−2.8,−1.2)

, h +

=(1,0.8)

. The second-stage solution is y =(0,1)

and

(

)=3. For h =(−2, −3)

, h +

=(1.8, 0)

, y =(0, 1)

with

(

)=3 . Taking the expectation, we obtain

(

)=3 . Thus, z

= z(x

(

)=−3.631 + 3 = −0.631 .

Step 4.Set ¯z = z

= −0.631 .

Step 5. Find discontinuity points of

(·) .For

, discontinuity points are all in-

tegers and all integers +0.8 . Thus, from

= 3.488 , we may branch at 3 or

3.8.For

, discontinuity points are all integers and all integers +0.2 . Thus, from

= 1.887 , we may only branch at 2 (since 1.2 is outside the bounds). Say, we

branch at

= 3 . Create two new hypercubes, both having the same lower bound:

=(3,6] × (1.4,7.5] , with

= −2.131 and H

=(1.4,3] ×(1.4,7.5] , with

= −2.131 .

= {H

Iteration 2:

Step 1.

= 2 . Select H

= H

and remove it from the list.

Step 2. l

=(3,1.4)

=(6,7.5)

e)=

(3.1,1.5)=

(3.8,2)

(

)=3.

Step 3. Create a new current problem, with a lower bound of 3.1 for

(instead of 1.5 ) and a lower bound 3 for

. The solution of the current prob-

lem is x

=(0.408,2.008)

=(4.425,2.825)

and CP(l

)=−2.037 .

Compute the value of

(

(4.425,2.825)=

(4.8,3) .For h =(−2.8, −1.2)

=(2,1.8)

. The second-stage solution is y =(1,0)

and

(

)=4.4.For

h =(−2, −3)

, h+

=(2.8, 0)

, y =(1, 0)

with

(

)=3 . Taking expecta-

tion, we get

(

)=3.7 . Thus, z

= z(x

)=c

x2+

(

)=−5.037+3.7 =

−1.337 .

Step 4.Set ¯z = z

= −1.337 .

Step 5. Find discontinuity points of

(·) .From

= 4.425 , we may branch at 4 or

4.8.From

= 2.825 , we may branch at 2.2 or 3.Say,webranchat

= 2.2.

Create two new hypercubes H

=(3,6] ×(2.2, 7.5] and H

=(3,6] ×(1.4,2.2] ,

with

= −2.037 .

= {H

Iteration 3:

310 7 Stochastic Integer Programs

Step 1.

= 3 . Select H

= H

and remove it from the list.

Step 2. l

=(1.4, 1.4)

=(3,7.5)

e)=

(1.5,1.5)=1.5.

Step 3. The solution of the current problem is x

=(0.406,1.297)

(3,2.109)

and CP(l

)=−2.109 .

(

(3,2.2)=3andz

=z(x

−0.609 .

Step 4.¯z is unchanged.

Step 5. Find discontinuity points of

(·) .From

= 2.109 , we may branch at

2or2.2.Saywebranchon

= 2 . Create two new hypercubes H

=(1.4, 3] ×

(2,7.5] and H

=(1.4, 3]×(1.4, 2] , with

= −3.25 .

= {H

Iteration 4:

Step 1.

= 4 . Select H

= H

and remove it from the list.

Step 2. l

=(3,2.2)

=(6,7.5)

e)=

(3.1,2.3)=3.7.

Step 3. The solution of the current problem is x

=(0.554,2.154)

=(4.863,

3.262)

and CP(l

)=−1.994 .

(

(5,4)=5.2andz

= z(x

)=−5.694 + 5.2 = −0.494 .

Step 4.¯z is unchanged.

Step 5.From

= 4.863 , we may branch at 4.8or5.From

= 3.262 , we

may branch at 3.2or4.Say,webranchat

= 4.8 . Create two new hypercubes

=(4.8,6] ×(2.2,7.5] and H

=(3,4.8] ×(2.2,7.5] , with

= −1.994 .

= {H

Iteration 5:

Step 1.

= 5 . Select H

= H

and remove it from the list.

Step 2. l

=(3,1.4)

=(6,2.2)

e)=

(3.1,1.5)=3.

Step 3. The solution of the current problem is x

=(0,2.2)

=(4.4, 2.2)

and

CP(l

)=−1.4.

(

(4.8,2.2)=3andz

= z(x

)=−4.4 + 3 =

−1.4

Step 4.Set ¯z = z

= −1.4.

Step 5. CP(l

) ≥ ¯z . Fathom. This is the situation described in Exercice 1 below.

= {H

Iteration 6:

Step 1.

= 6 . To speed up things, select H

= H

and remove it from the list.

Step 2. l

=(3,2.2)

=(4.8,7.5)

e)=

(3.1,2.3)=3.7.

7.3 Second-stage Integer Variables 311

Step 3. The solution of the current problem is x

=(0.594,2.103)

(4.8,3.291)

and CP(l

)=−1.991 .

(

(4.8,4)=5.2andz

z(x

)=−5.691 + 5.2 = −0.491 .

Step 4.¯z is unchanged.

Step 5. Find discontinuity points of

(·) .From

= 3.291 , we branch at

3.2 . Create two new hypercubes H

=(3,4.8] ×(3.2, 7.5] and H

=(3,4.8] ×

(2.2,3.2] , with

= −1.993 .

= {H

Iteration 7:

Step 1.

= 7 . To speed up things, select H

= H

and remove it from the list.

Step 2. l

=(3,2.2)

=(4.8,3.2)

e)=

(3.1,2.3)=3.7

Step 3. The solution of the current problem is x

=(0.533,2.133)

=(4.8,3.2)

and CP(l

)=−1.9.

(

(4.8,3.2)=3.2andz

= z(x

)=−5.6 +

3.7 = −1.9.

Step 4.Set ¯z = z

= −1.9.

Step 5. CP(l

) ≥ ¯z . Fathom.

= {H

Subsequent iterations.

The current solution

=(4.8, 3.2)

with z

= −1.9 is in fact the optimal one.

(In a small problem like this one, this can be checked by solving the full determinis-

tic equivalent.) Of the remaining hypercubes, only H

will be fathomed directly by

the value of the current problem (−1.664) . The other three hypercubes will need

extra branchings. Note that the lower bounds

s have not been used for the selec-

tion of the hypercubes in Step 1, as this would have yet augmented the number of

iterations. Also, they could not be used to fathom hypercubes, as all lower bounds

were smaller than the optimum.

Faster fathoming is expected if better bounds can be obtained. One way to get

those would be to have a full description of the second-stage continuous recourse

function, for instance by sending all possible Benders cuts. In the current example,

the value of the current problem would have been improved only on H

A number of implementation aspects have been omitted in the presentation as

well as in the example. They can be found in Ahmed, Tawarmalani and Sahinidis

[2004]. This includes how to ﬁnd the smallest initial hypercube or how to choose an

effective partitioning component. Earlier work on integer second-stage includes de-

composition of test sets (Hemmecke and Schultz [2003]) or Gr¨obner basis reduction

techniques (Schultz, Stougie, van der Vlerk [1998]). For the case of integer ﬁrst- and

second-stage and random right-hand side only, Kong, Schaefer and Hunsaker [2006]

develop a superadditive dual approach.

312 7 Stochastic Integer Programs

Exercises

1. In the branching-on-tenders algorithm, show that if

(

e) ,then

no branching occurs in Step 5.

2. Consider the second-stage constraints as in Example 3. Compare two situations:

• h is a random vector with two independent components, each taking all

integer values between −1and−6 independently;

• h can take four values: (−2,−2.4)

, (−3.8,−3.5)

(−4.6,−4.1)

and (−5.2,−5.3)

Which one is likely to create more discontinuity points in

(·) ?

7.4 Reformulation

To illustrate reformulation, assume a discrete random variable and a ﬁxed re-

course matrix. Also assume binary second-stage decision variables. The value of

the second-stage program for one realization

reads as

Q(x,

)=min

y |Wy ≥ h

−T

x , y ∈{0,1}

} (4.1)

where, as usual, the index k = 1,...,K is used for the K realizations of ξ .The

LP-relaxation of this program is

C(x,

)=min

y |Wy ≥h

−T

x , 0 ≤y ≤e} . (4.2)

The idea of reformulation is to modify the original formulation of {y |Wy ≥ h

−

x , 0 ≤y ≤ e} by adding a number of so-called valid inequalities or cuts that will

reduce the number of fractional solutions. A large variety of valid inequalities have

been proposed in integer programming. The choice of an appropriate class of valid

inequalities depends on the structure of the LP-relaxation. Valid inequalities are

routinely used in so-called branch-and-cut systems. Section 7.8b. provides simple

examples of valid inequalities in deterministic models. We use these examples to

illustrate the extra difﬁculties in stochastic integer programs.

a. Difﬁculties of reformulation in stochastic integer programs

Example 5

Consider the following second-stage program:

7.4 Reformulation 313

Q(x,

)=min 3y

+ 7y

+ 9y

+ 6y

s. t. 2y

+ 4y

+ 5y

+ 3y

≥ h −Tx ,

,...,y

∈{0,1} .

Assume two realizations of ξ =(h,T ) , h −Tx= 10 −2x

−4x

and 11 −4x

−

for k = 1,2 , with probability 0.25 and 0.75 , respectively. Consider a current

iterate x

=(0.3,0.6)

. The second-stage program for x = x

and ξ =

Q(x

)=min 3y

+ 7y

+ 9y

+ 6y

(4.3)

s. t. 2y

+ 4y

+ 5y

+ 3y

≥ 7 ,

,...,y

∈{0,1} .

The LP-relaxation of (4.3) has a fractional solution y =(1,1,0.2, 0)

. The cover

inequality y

≥1 is a valid inequality and, as shown in Section 7.8b., it sufﬁces

to provide an extended LP-relaxation

C(x

)=min 3y

+ 7y

+ 9y

+ 6y

(4.4)

s. t. 2y

+ 4y

+ 5y

+ 3y

≥ 7 ,

+ y

≥ 1 ,

0 ≤ y

,...,y

≤ 1 ,

having an integer optimal solution y =(1,0,1, 0)

If we consider ξ =

, the r.h.s. of the initial constraint becomes 8 . The LP-

relaxation has a fractional solution y =(1, 1,0.4,0)

and two cuts are needed to

obtain the extended LP- relaxation:

C(x

)=min 3y

+ 7y

+ 9y

+ 6y

(4.5)

s. t. 2y

+ 4y

+ 5y

+ 3y

≥ 8 ,

+ y

≥ 2 ,

+ y

≥ 1 ,

0 ≤ y

,...,y

≤ 1 ,

having an integer optimal solution y =(0,0,1, 1)

The extra difﬁculty in stochastic integer program is that the second stage pro-

gram is dependent on x .For ξ =

, we have obtained reformulation (4.4)for

x =(0.3,0.6)

. If we consider another iterate point, say x

=(0.5,0.25)

,then

the knapsack constraint in Q(x

) obtains a r.h.s. of 8 and the appropriate refor-

mulation is the same as in (4.5).

Thus, the reformulation of the second-stage of a stochastic integer program is

faced with two difﬁculties: a reformulation is needed for each realization of the

random vector and the reformulation must be made dependent on the value of the

ﬁrst-stage variables.