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

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

334 7 Stochastic Integer Programs

Exercises

1. In Example 9, assume a given construction delay for the warehouses in the sec-

ond stage. Is it still possible to decompose the second stage?

7.8 Short Reviews

a. Branch-and-bound

Consider the following integer program

z = min 3y

+ 2y

s. t. 2y

+ 3y

≥ 9 ,

−3y

+ 3y

≤ 5 ,

≥ 0 , integer

Optimize: First consider the LP-relaxation, i.e. the same problem where the

requirement “ y integer” is removed. Its solution is easily obtained through

your favorite LP-solver or through a graphical method. It is z = 7.333 , y =

(0.8,2.467)

.Let Y denote the second-stage polyhedron for this relaxation.

Bounding: On any polyhedron, the integer solution is no better than the contin-

uous one. The objective value of the LP-relaxation is thus a lower bound on the

solution of the integer program. It can be rounded down as the objective must be

integer, so z

= 8.Wemaytake ¯z = ∞ ,where z and ¯z denote lower and upper

bounds on the optimal solution.

Branching: as y is fractional, we may branch on either component. Say we

branch on y

. The current value is y

= 2.467 . Any integer solution must sat-

isfy either y

≤ 2ory

≥ 3 . This dichotomy excludes the current solution.

It does not eliminate any integer point. Branching consists of considering two

nodes: Y

= Y ∩{y

≤ 2} and Y

= Y ∩{y

≥ 3} . The list of nodes is denoted

= {Y

Select a Node and Reoptimize: We (arbitrarily) select Y

and reoptimize the

LP-relaxation on Y

. Its solution is z = 8.5, y =(1.5,2)

Branching: as y

= 1.5 is fractional, we create two new nodes: Y

= Y

∩{y

≤

1} and Y

= Y

∩{y

≥ 2}. Y

is removed from the list.

= {Y

Select a Node and Reoptimize: We select Y

and reoptimize the LP-relaxation

on Y

. It has no feasible solution. Y

is fathomed. This means it is removed

from the list and does not need any further branching (which would not help in

creating a feasible solution).

= {Y

Select a Node and Reoptimize: We select Y

and reoptimize the LP-relaxation.

Its solution is z = 9.333 , y =(2, 1.667)

7.8 Short Reviews 335

Branching: as y

= 1.667 is fractional, we create two new nodes: Y

= Y

∩{y

≤

1} and Y

= Y

∩{y

≥ 2}. Y

is removed from the list.

= {Y

Select a Node and Reoptimize: We select Y

and reoptimize the LP-relaxation.

Its solution is z = 11 , y =(3,1)

Updating the Incumbent: As y is integer and z < ¯z , the best feasible solution

becomes y =(3,1)

and ¯z = 11 . Y

is fathomed (as they are no better integer

solutions in Y

= {Y

Select a Node and Reoptimize : We select Y

and reoptimize the LP-relaxation.

Its solution is z = 10 , y =(2,2)

Updating the Incumbent: As y is integer and z < ¯z , the best feasible solution

becomes y =(2,2)

and ¯z = 10 . Node Y

is fathomed.

= {Y

Select a Node and Reoptimize: We select Y

and reoptimize the LP-relaxation.

Its solution is z = 10 , y =(1.333,1)

. Y

is fathomed: no solution in Y

can be

better than 10 , which is the value of the current best solution. The list is empty.

The algorithm terminates with optimal solution y =(2,2)

and z = 10 .

To summarize, branching occurs at nodes having a fractional solution. Fathom-

ing occurs when the LP-relaxation of a node is infeasible, has an integer solution or

has a solution whose value is worse than the current incumbent. Branch-and-bound

is only a part of the techniques used for solving large MIP’s. It is combined with cut

generation, reduced cost ﬁxing, preprocessing, special-ordered set (SOS) or gener-

alized upper bound (GUB) branching, and primal heuristics to cite some of the most

important.

b. A simple example of valid inequalities

Consider the following binary program

min 3y

+ 7y

+ 9y

+ 6y

s. t. 2y

+ 4y

+ 5y

+ 3y

≥ 7 ,

,...,y

∈{0,1} .

The so-called cover inequalities can be found by a simple reasoning. If we con-

sider a solution s.t. y

= y

= 0 , the constraint cannot be satisﬁed. Thus, at least

one of the two variables must be 1 . This can be expressed as

+ y

≥ 1,

which is a cover inequality. It is said to be valid as it must be satisﬁed by any binary

solution. At the same time, it cannot replace the original constraint.

Similarly, the original constraint cannot be satisﬁed if y

= y

= 0, orif y

= y

= 0 implying

336 7 Stochastic Integer Programs

+ y

≥ 1 ,

+ y

≥ 1 .

respectively.

Three comments are in line here. First, there are more valid inequalities than the

above three. For instance, y

+ y

≥ 1 is also valid. However, it is implied by

+ y

≥ 1 . Second, reformulation of an integer program with several constraints

may lead to a very large number of valid inequalities. In practice, the idea is to only

add those which are violated at the current iterate point. Going back to our example,

its LP solution is y =(1,1,0.2,0)

. (This is easily checked as the variables in

the example are put in increasing order (3/2 ≤ 7/4 ≤ 9/5 ≤ 6/3) of the ratio

between the objective coefﬁcient and the constraint coefﬁcient.) Of the four valid

inequalities, only the ﬁrst one y

+ y

≥ 1 is violated, as y

+ y

= 0.2 . Adding

+ y

≥1 reduces the number of fractional solutions without changing the binary

solutions. It turns out that the LP with the addition of the cut y

+ y

≥ 1hasa

spontaneous optimal integer solution y =(1,0,1, 0)

which is thus the optimal

solution of the integer program.

Third, the valid inequalities depend on the r.h.s. Consider the solution of the same

problem where the right-hand side is 8 :

min 3y

+ 7y

+ 9y

+ 6y

s. t. 2y

+ 4y

+ 5y

+ 3y

≥ 8 ,

,...,y

∈{0,1} .

The non-dominated valid inequalities become: y

+ y

≥ 2andy

+ y

≥ 1.

The ﬁrst inequality can be justiﬁed as follows: if y

= 1,then 4y

+ 5y

+ 3y

≥ 6

must hold, which requires at least two variables to be 1 . Note that this inequality

is not valid when the r.h.s. is 7 . A constraint like y

+ y

≥ 1 is still valid but

dominated by y

+ y

≥ 2.

The solution of the LP relaxation is y =(1, 1,0.4,0)

. It violates the cut y

+ y

≥2 . The LP relaxation with the addition of this single cut gives a fractional

solution. The LP relaxation with the addition of y

+ y

≥ 2andy

+ y

≥ 1

gives the optimal solution y =(0, 0,1,1)

c. Disjunctive cuts

c.1 Union of Sets

Proposition 17. If P

= {x ∈ ℜ

x ≥b

} for i = 0,1 are two nonempty polyhe-

dra, then

x ≥

is a valid inequality for co(P

∪P

) if and only if there exists

≥ 0 such that

≥ (u

)

and

≤ (u

)

for i = 0,1 .

7.8 Short Reviews 337

Proof:LetP

= {x ∈ ℜ

x ≥b

} for i = 0, 1 be two nonempty polyhedra. We

search for a valid inequality for co(P

∪P

) . Any nonnegative combination of the

constraints in one of the P

’s gives a valid constraint for that P

.Let u

≥0bethe

vector representing this combination. Thus (u

)

x ≥ (u

)

is valid for P

.If

we do the same in both sets, we may construct a valid inequality for co(P

∪P

) of

the form

x ≥

by taking

≥ (u

)

and

≤ (u

)

for i = 0,1 . Indeed,

if x ∈ co(P

∪P

) , it must belong to one of the two polyhedra. Say it belongs to

. Then,

x ≥ (u

)

x ≥(u

)

≥

which proves the validity of the cut.

Example:Let P

= {x ∈ℜ

| x

≤ 1 , x

≤ 3} and P

= {x ∈ℜ

| 4x

+ 2.5x

≤

10}.

Say, we want a disjunctive cut that separates the current point x

=(1.8,2.4)

Then, the cut is obtained by solving an LP consisting of maximizing the violation

−

, under the constraints of Proposition 11. To be bounded, this LP needs

some normalizing. One possibility is to take −1 ≤

≤1, −e ≤

≤e . We obtain:

z = max

−1.8

−2.4

s. t.

≥−u

≥−4u

≥−u

≥−2.5u

≤−u

−3u

≤−10u

u ≥ 0 , −e ≤

≤ e , −1 ≤

≤ 1 .

The solution is z = 0.2, u

= 0.4, u

= 0.2, u

= 0.1,

=(−0.4,−0.2)

= − 1 . The disjunctive cut is −0.4x

−0.2x

≥−1.At x

=(1.8,2.4)

,the

cut is violated by 0.2 which is the value of z . The cut can also be written as

+ x

≤ 5 . The line 2x

+ x

= 5 passes through (1, 3)

and (2.5,0)

,which

are extreme points of P

and P

, respectively.

c.2 Disjunction on a binary variable

We consider the disjunction P

= Y ∩{y ∈ ℜ

| y

≤ 0} and P

= Y ∩{y ∈ ℜ

≥ 1} for some fractional variable.

Proposition 18. The inequality

y ≥

is valid if and only if there exists

≥ 0 for i = 0,1 such that

≥ (u

)

W −v

−w

≥ (u

)

W −v

+ w

≥ (u

)

d −e

≥ (u

)

d −e

+ w

338 7 Stochastic Integer Programs

The cut is obtained by solving an LP consisting of maximizing the violation

−

, under the constraints deﬁned in Proposition 12, where y

is the current

fractional solution. To be bounded, this LP needs some normalizing. One possibility

is to take −1 ≤

≤ 1, −e ≤

≤ e .

Example: Consider again the program:

min 3y

+ 7y

+ 9y

+ 6y

s. t. 2y

+ 4y

+ 5y

+ 3y

≥ 7 ,

,...,y

∈{0,1} .

Its LP relaxation has solution y =(1,1,0.2, 0)

(see Section 7.8b.). y

is the only

fractional variable and is thus used for the disjunction:

= {y ≥ 0 |2y

+ 4y

+ 5y

+ 3y

≥ 7 ,

≤ 1 , y

≤ 1, y

≤ 1 , y

≤ 0}

and P

= {y ≥ 0 |2y

+ 4y

+ 5y

+ 3y

≥ 7 ,

≤ 1, y

≤ 1 , y

≥ 1}

= {y ≥ 0 |2y

+ 4y

+ 5y

+ 3y

≥ 7 ,

−y

≥−1 , − y

≥−1 , −y

≥−1 , − y

≥−1 ,−y

≥ 0}

and P

= {y ≥ 0 |2y

+ 4y

+ 5y

+ 3y

≥ 7 ,

−y

≥−1 , − y

≥−1 , −y

≥−1 , − y

≥−1 , y

≥ 1} .

The disjunctive cut is obtained through the solution of:

z = max

−

−0.2

s. t.

≥ 2u

−v

≥ 2u

−v

≥ 4u

−v

≥ 4u

−v

≥ 5u

−v

−w

≥ 5u

−v

+ w

≥ 3u

−v

≥ 3u

−v

≤ 7u

−v

≤ 7u

−v

+ w

u,v,w ≤ 0 , −e ≤

≤ e , −1 ≤

≤1 .

The solution is z = 0.8/3, u

= 1/3, v

=(2/ 3,4/3,0,0)

, w

= 4/3, u

= 0,

=(0,0,0,0)

, w

= 1/3,

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

= 1/3 . The disjunctive cut

is 1/3y

+ y

≥ 1/3 , which is currently violated by 0.8/3 . Note however that it is

dominated by the cut y

+ y

≥ 1 (the cover inequality in Section 7.8b.).

Part IV

Approximation and Sampling Methods

Chapter 8

Evaluating and Approximating Expectations

The evaluation of the recourse function or the probability of satisfying a set of con-

straints can be quite complicated. This problem is basically one of numerical in-

tegration in high dimensions corresponding to the random variables. The general

problem requires some form of approximation, such as quadrature formulas, which

typically apply to smooth functions in low dimensions without using known con-

vexity properties. In Section 8.1 of this chapter, we review some of these basic

procedures, but note that stochastic programs often do not have differentiability as

assumed in many numerical schemes but generally do have useful convexity prop-

erties.

In the remaining sections of this chapter, we consider approximations that give

lower and upper bounds on the expected recourse function value in two-stage prob-

lems. The intent of these procedures is to provide progressively tighter bounds until

some a priori tolerance has been achieved. This chapter focuses on such determin-

istic approximation results for two-stage problems. In Chapter 9, we describe ap-

proximations for two-stage problems built on Monte Carlo sampling. Chapter 10

discusses both deterministic and random approximation methods for the multistage

case.

Section 8.2 in this chapter discusses the most common type of approximations

built on discretizations of the probability distribution. The lower bounds are exten-

sions of midpoint approximations, while the upper bounds are extensions of trape-

zoidal approximations. The bounds are reﬁned using partitions of the region. Other

improvements are possible using more tightly constrained moment problem models

of the approximation, as described in Section 8.5.

Section 8.3 discusses computational uses for bounds. The goal is to place the

bounds effectively into computational methods. We present uses of the bounds in

the L -shaped method, inner linearizations, and separable nonlinear programming

procedures. Section 8.4 discusses some basic bounding approaches for probabilis-

tic constraints. General forms are presented brieﬂy. These methods are based on

fundamental inequalities from probability.

Section 8.5 presents a variety of extensions of the previous bounding approaches.

It presents bounds based on approximations of the recourse function. The basic idea

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

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

 Springer Science+Business Media, LLC 2011

342 8 Evaluating and Approximating Expectations

is to bound the objective function above and below by functions that are simply inte-

grated, such as separable functions. We present the basic separable piecewise linear

upper bounding function and various methods based on this approach. We also dis-

cuss results for particular moment problem solutions. We consider bounds based on

second moment information and allowances for unbounded support regions. Finally,

Section 8.6 concludes this chapter with basic results on convergence of approxima-

tions and bounding procedures. Most of the following results are based on these

convergence ideas.

8.1 Direct Solutions with Multiple Integration

In this section, we again consider the basic stochastic program in the form

min

x + Q(x) | Ax = b , x ≥ 0} , (1.1)

where Q is the expected recourse function,



[Q(x,

)]P(d

) , where we use

P(d

) in place of dF(

) to allow for general probability measure convergence.

We again have

Q(x,

)=min

)

{q(

)

) | Wy(

)=h(

) − T(

)x , y(

) ≥ 0} , (1.2)

where we assume two stages and no probabilistic constraints for now.

As we mentioned previously, we can always treat (1.1) as a standard nonlinear

program if we can evaluate Q(x) and perhaps its derivatives. The major difﬁculty

of stochastic programming is, of course, just such an evaluation. These function

evaluations all involve multiple integration with potentially large numbers (on the

order of 1000 or more) of random variables. This section considers some of the

basic techniques from numerical integration that have been attempted in the context

of stochastic programming. Remaining sections consider various approximations

that lead to computable problems.

Numerical integration procedures are generally built around formulas that ap-

ply only in small dimensions (see, e.g., Stroud [1971]). For some special functions

deﬁned over speciﬁc regions, efﬁcient computations are possible, but these results

do not generally carry over to the more general setting of the integrand, Q(x,

) .

This function is piecewise linear in (1.2) as a function of

and, hence, has many

nondifferentiablepoints. The error analysis from standard smooth integrations (built

on Peano’s rule) cannot apply. In fact, quadrature formulas built on low-order poly-

nomials may produce poor results when other simple calculations are exact (Exer-

cise 1).

Generalizations of the basic trapezoid and midpoint approaches in numerical in-

tegration obtain bounds, however, when convexity properties of Q are exploited.

Problem structure is in fact a key to obtaining computable approximations of the

multiple integral.

8.1 Direct Solutions with Multiple Integration 343

The simple recourse example is the best case for exploitation of problem struc-

ture. In this case, Q(x,

) becomes separable into functions of each component

of h(

) , the right-hand side vector in (1.2). We obtain Q(x)=

∑

i=1

(x) as in

(3.1.9), which only requires integration with respect to each h

separately. As we

described in Chapter 5, this allows the use of general nonlinear programming algo-

rithms.

In general, the stochastic linear program recourse function can also be written in

terms of bases in W . Suppose the set of bases in W is {B

,i ∈ I} .Let

(

)

−1

.Then

Q(x,

)=max

{

(

)

(h(

) −T(

)x) |

(

)

W ≤ q(

)

} , (1.3)

where, if q(

) is constant (i.e., not random), the evaluation reduces to ﬁnding the

maximum value of the inner product over the same feasible set for all

. With

) constant,

Q(x)=

∑

i∈I



{

(h(

) −T(

)x)}P(d

) , (1.4)

where

= {

(h(

) −T (

)x) ≥

(h(

) −T (

)x ), j = i}. The integrand

in (1.4) is linear; so, we have

Q(x)=

∑

(

−

x) , (1.5)

where



P(d

) and



P(d

) . Thus, if each

can be found,

then the numerical integration reduces to ﬁnding the expectations of the random

parameters over the regions

, i.e., the conditional expectation on

.Inthis

case, we can also deﬁne a basis B

from W so that B

= q and then

= {

−1

(h(

) −T(

)x)) ≥ q

−1

(h(

) −T(

)x)),∀j = i}. If integration over

the regions

deﬁned by B

is sufﬁciently straightforward, then (1.5) can be used

directly. We illustrate this with the following example, which we will also use for

bounding approximations in the following sections.

Example 1

Consider the following recourse problem with only h random:

Q(x,ξ)=min y

+ y

−

+ y

−

+ y

s. t. y

−y

−

+ y

= h

−x

−y

−

+ y

= h

−x

−

, y

−

, y

≥ 0 ,