Birge J.R., Louveaux F. Introduction to Stochastic Programming
Подождите немного. Документ загружается.
324 7 Stochastic Integer Programs
s. t. 20x
11
+ 30x
21
≤ 100 , y
1
(ξ) ≤ ξ
1
25x
12
+ 25x
22
≤ 100 , y
2
(ξ) ≤ ξ
2
,
4x
11
+ 7x
12
+ 6x
21
+ 5x
22
≤ 36 , y
1
(ξ) ≤ x
11
+ x
12
,
x
ij
≥ 0integer, y
2
(ξ) ≤ x
21
+ x
22
,
y
1
(ξ),y
2
(ξ) ≥ 0integer.
Letting y
+
i
(
ξ
)=
ξ
i
−y
i
(
ξ
) , one obtains an equivalent formulation,
min 3x
11
+ 2x
12
+ 4x
21
+ 5x
22
+ E
ξ
{4y
+
1
(ξ)+6y
+
2
(ξ)}−30
s. t. 20x
11
+ 30x
21
≤100 , y
+
1
(ξ) ≥ ξ
1
−
χ
1
,
25x
12
+ 25x
22
≤100 , y
+
2
(ξ) ≥ ξ
2
−
χ
2
,
4x
11
+ 7x
12
+ 6x
21
+ 5x
22
≤36 ,
y
+
1
(ξ),y
+
2
(ξ) ≥ 0 and integer,
x
11
+ x
12
=
χ
1
, x
21
+ x
22
=
χ
2
,
x
ij
≥0 and integer.
This representation puts the problem under the form of a simple recourse model
with expected shortage only.
Let us start with the null solution, x
ij
= 0,
χ
i
= 0, i, j = 1, 2 with
θ
i
= −∞ , i =
1,2 . We compute u(0)=Eξ
+
=
μ
+
= 3 ; hence
Ψ
1
(0)=12 ,
Ψ
2
(0)=18 , where
we have dropped the constant, −30 , from the objective for these computations.
To construct the first optimality cuts, we also compute u(1)=u(0) −1 + F(0)=
2 + .05 = 2.05 . Thus, E
11
= 4(3 −2.05)=3.8, e
11
= 4(1 ∗3 −0 ∗2.05)=12 ,
defining the optimality cut
θ
1
+ 3.8
χ
1
≥12 . As
χ
2
=
χ
1
, E
21
and e
21
are just 1.5
times E
11
and e
1
, respectively, yielding the optimality cut
θ
2
+ 5.7
χ
2
≥ 18 .
The current problem becomes
min 3x
11
+ 2x
12
+ 4x
21
+ 5x
22
−30+
θ
1
+
θ
2
s. t. 20x
11
+ 30x
21
≤ 100 , 25x
12
+ 25x
22
≤ 100,
4x
11
+ 7x
12
+ 6x
21
+ 5x
22
≤ 36 ,
x
11
+ x
12
=
χ
1
, x
21
+ x
22
=
χ
2
,
θ
1
+ 3.8
χ
1
≥ 12 ,
θ
2
+ 5.7
χ
2
≥ 18 ,
x
ij
≥ 0 , integer.
We obtain the solution x
11
= 0, x
12
= 4, x
21
= 1, x
22
= 0,
θ
1
= − 3.2,
θ
2
=
12.3 . We compute u(4)=u(0)+
∑
3
l=0
(F(l)−1)=0.31936 and
Ψ
1
(4)=1.277 >
θ
1
. A new optimality cut is needed for
Ψ
1
(·) . Because
Ψ
(5)=0.5385 , the cut is
0.739
χ
1
+
θ
1
≥ 4.233 . We also have u(1)=2.05 , hence
Ψ
2
(1)=12.3 =
θ
2
,so
no new cut is generated for
Ψ
2
(·) .
At the next iteration, with the extra optimality cut on
θ
1
, we obtain a new so-
lution of the current problem as x
11
= 0, x
12
= 2, x
21
= 3, x
22
= 0,
θ
1
= 4.4,
θ
2
= 0.9 . Here, two new optimality cuts are needed:
7.5 Simple Integer Recourse 325
2.312
χ
1
+
θ
1
≥ 9.623
and
2.117
χ
2
+
θ
2
≥ 10.383 .
The next iteration gives x
11
= 0, x
12
= 3, x
21
= 2, x
22
= 0,
θ
1
= 2.688 ,
θ
2
=
6.6 as a solution of the current problem. Because
Ψ
2
(2)=7.5 >
θ
2
, a new cut is
generated, i.e., 3.467
χ
2
+
θ
2
≥ 14.435 . The next iteration point is x
11
= 0, x
12
=
3, x
21
= 2, x
22
= 0,
θ
1
= 2.688 ,
θ
2
= 7.5 , which is the optimal solution with
total objective value −5.812 .
b. Thecasewhere S = 1 ,
χ
not integral
Details can again be found in Louveaux and van der Vlerk [1993]; we illustrate
the results with an example. Consider Example 6 but with the x
ij
’s continuous.
Because we still assume the random variables follow a Poisson distribution, the
example indeed falls into the category S = 1 ; only integer realizations are possible.
For a given component i ,the
ρ
i
-approximation rooted at an integer defines the
convex hull of the function
Ψ
i
(·) . All optimality cuts defined at integer points are
thus valid inequalities. If we take Example 6 again and impose all optimality cuts at
integer points, the continuous solution is x
11
= 0, x
12
= 3, x
21
= 2, x
22
= 0,and
no extra cuts are needed here. Now assume the objective coefficients of x
12
and x
21
are 1 and 4.5 (instead of 2 and 4 ). The solution of the stochastic program with
continuous first-stage decisions and all optimality cuts imposed at integer points
becomes x
11
= 0, x
12
= 4, x
21
= 1.33 , x
22
= 0 , and thus,
χ
1
= 4,
χ
2
= 1.33 .
We now illustrate how to deal with a noninteger value of some
χ
i
.Now,
u(1.33)=3 −1 + F(0)=2.05 and therefore
Ψ
2
(1.33)=12.3 >
θ
2
. This requires
imposing a new optimality cut . By Lemma 15, we know
Ψ
2
(.) is constant within
(1,2) with value 12.3.Let
δ
a
= 1if
χ
2
> 1and0otherwise,
δ
b
= 1if
χ
2
< 2and0otherwise.
The cut imposes that
θ
2
≥12.3if1<
χ
2
< 2,i.e.,if
δ
a
=
δ
b
= 1 . This is realized
by the following constraints:
χ
2
≤ 1 + 10
δ
a
,
χ
2
≥ (1 +
ε
)
δ
a
,
χ
2
≤ 10 −(8 +
ε
)
δ
b
,
χ
2
≥ 2 −2
δ
b
,
θ
2
≥ 12.3 −100(2 −
δ
a
−
δ
b
) ,
where 10 and 100 are sufficiently large numbers to serve as bounds on
χ
2
and
−
θ
2
, respectively, and
ε
is a very small number. Thus, defining a function
Ψ
i
(·)
to be constant in some interval requires two extra binary variables and three extra
326 7 Stochastic Integer Programs
constraints. It is thus reasonable to first consider optimality cuts that define the con-
vex hull.
Continuing the example, we solve the current problem with the three additional
constraints. The solution is x
11
= 0, x
12
= 3.43 , x
21
= 2, x
22
= 0 with
χ
1
= 3.43 ,
χ
2
= 2,
θ
1
= 2.08 ,
θ
2
= 7.5 . Thus, one more set of cuts is needed to define
Ψ
1
in the interval (3, 4) . The final solution is x
11
= 0, x
12
= 3, x
21
= 1, x
22
= 0,
θ
1
= 2.689 ,
θ
2
= 12.3,and z = −7.51 .
Exercises
1. The definition (3.3.5) of a two-stage stochastic program with simple recourse
shows that it is a particular case of a two-stage stochastic program with integer
second-stage. Explain why Lemma 15 is not identical to Propositions 8 and 9.
2. Similarly, for case where S = 1and
χ
is not integral, explain why the branch-
ing on tenders algorithm of Section 7.3 does not apply directly.
7.6 Cuts Based on Branching in the Second Stage
We now show how branching on the second-stage variables may create feasibility
or optimality cuts.
a. Feasibility cuts
As usual, let K
2
(
ξ
) denote the second-stage feasibility set for a given
ξ
and K
2
=
∩
ξ
∈
Ξ
K
2
(
ξ
) . Let also C
2
(
ξ
) denote the set of first-stage decisions that are feasible
for the continuous relaxation of the second stage, i.e.,
C
2
(
ξ
)={x |∃y s. t. Wy = h(
ω
) −T(
ω
)x , y ≥0} .
Clearly, K
2
(
ξ
) ⊂C
2
(
ξ
) , and any induced constraint valid for C
2
(
ξ
) is also valid
for K
2
(
ξ
) . Also, detecting that some point x ∈ C
2
(
ξ
) does not belong to K
2
(
ξ
)
amunts to solving a phase one problem:
(P1) w(x,
ξ
)=min e
T
v
+
+ e
T
v
−
s. t. Wy+ v
+
−v
−
= h(
ω
) −T(
ω
)x ,
y ∈ Z
n
2
+
, v
+
,v
−
≥ 0 . (6.1)
As usual, x ∈ K
2
(
ξ
) if and only if w(x,
ξ
)=0. If x ∈ K
2
(
ξ
) , we would like
to generate a feasibility cut . Let (y,v
+
,v
−
) be a solution to (P1), and because
7.6 Cuts Based on Branching in the Second Stage 327
x ∈K
2
(
ξ
) ,wehave w(x,
ξ
)=e
T
v
+
+e
T
v
−
> 0.If y ∈ Z
n
2
+
, then a cut of the form:
(5.1.3) can be generated. If y ∈ Z
n
2
+
, then some of the components of y are not
integer. A branch and bound algorithm can be applied to (P1). This will generate
a branching tree where, at each node, additional simple upper or lower bounds are
imposed on some variables.
Let
ρ
= 1,...,R index all terminal nodes, i.e., nodes that have no successors,
of the second-stage branching tree. Let Y
ρ
be the corresponding subregions. They
form a partition of ℜ
n
2
+
, i.e., ℜ
n
2
+
= ∪
ρ
=1,...,R
Y
ρ
and Y
ρ
∩Y
σ
= /0,
ρ
=
σ
.Now,
x ∈ K
2
(
ξ
) if and only if x ∈∪
ρ
=1,...,R
K
ρ
2
(
ξ
) ,where
K
ρ
2
(
ξ
)={x |∃y ∈Y
ρ
s. t. Wy ≤ h(
ω
) −T(
ω
)x , y ≥0} .
However, because Y
ρ
is obtained from ℜ
n
2
+
by some branching process, it is de-
fined by adding a number of bounds to some components of y . Thus, K
ρ
2
(
ξ
) is a
polyhedron for which linear cuts are obtained through a classical separation or du-
ality argument. It follows that x ∈ K
2
(
ξ
) if and only if at least one among R sets
of cuts is satisfied.
In practice, one constructs the branching tree of the second stage associated with
one particular ¯x and generates one cut per terminal node of the restricted tree. This
means that one first-stage feasibility cut (8.1.3) corresponds to the requirement that
one out of R cuts is satisfied. As expected, this takes the form of a Gomory function.
It can be embedded in a linear programming scheme by the addition of extra binary
variables, one for each of the R cuts, as follows. Assume the
ρ
th cut is represented
by u
T
ρ
x ≤ d
ρ
. One introduces R binary variables,
δ
1
,...,
δ
R
. The requirement that
at least one of the R cuts is satisfied is equivalent to
u
T
ρ
x ≤ d
ρ
+ M
ρ
(1 −
δ
ρ
) ,
ρ
= 1,...,R ,
R
∑
ρ
=1
δ
ρ
≥ 1 ,
δ
ρ
∈{0,1} ,
ρ
= 1,...,R ,
where M
ρ
is a large number such that u
T
ρ
x ≤ d
ρ
+ M
ρ
, ∀x ∈ K
1
.
Finally, observe that x ∈ K
2
if and only x ∈ K
2
(
ξ
) , ∀
ξ
∈
Ξ
. As in the con-
tinuous case (Section 5b.), it is sometimes enough to consider x ∈ K
2
(
ξ
) for one
particular
ξ
.
Example 7
Consider again Example 3.3, when the second stage is defined as
−y
1
+ y
2
≤ξ −x
1
,
y
1
+ y
2
≤2 −x
2
, y
1
,y
2
≥ 0 and integer,
328 7 Stochastic Integer Programs
where ξ takes on the values 1 and 2 with equal probability 0.5 . It suffices here
to consider x ∈ K
2
(1) because K
2
(1) ⊂ K
2
(2) . First, consider x =(2,2)
T
.From
Section 5.1, we find a violated continuous induced constraint:
x
1
+ x
2
≤ 3 .
Next, consider x =(1.4,1.6)
T
. Problem (P1) is
min v
1
+ v
2
s. t. −y
1
+ y
2
−v
1
≤−0.4 ,
y
1
+ y
2
−v
2
≤ 0.4,
y
1
,y
2
≥ 0 and integer,
where v
1
and v
2
correspond to v
−
in (6.1)and v
+
is not needed due to the
inequality form of the constraints. The optimal solution of the continuous relaxation
of (P1) is given by the following dictionary:
w = v
1
+ v
2
,
y
1
= 0.4 + y
2
+ s
1
−v
1
,
s
2
= 0 −2y
2
−s
1
+ v
1
+ v
2
.
Its solution is w = 0 , which implies x ∈C
2
(1) .However, y
1
is not integer. Branch-
ing creates two nodes, y
1
≤ 0andy
1
≥ 1 , respectively. In the first branch, the
bound y
1
≤ 0 creates the additional constraint y
1
+ s
3
= 0 . After one dual itera-
tion, the following optimal dictionary is obtained:
w = 0.4 + y
2
+ s
1
+ s
3
+ v
2
,
y
1
= 0 −s
3
,
s
2
= 0.4 −y
2
+ s
3
+ v
2
,
v
1
= 0.4 + y
2
+ s
1
+ s
3
.
Associating the dual variables (−1,0, −1) with the right-hand sides ( 1 −x
1
,2−
x
2
, 0 ), one obtains the feasibility cut , x
1
−1 ≤ 0 , for this branch.
Similarly, in the second branch, the bound y
1
≥ 1 creates a constraint y
1
−s
3
=
1 . After two dual iterations, the optimal dictionary is:
w = 0.6 + y
2
+ s
2
+ s
3
+ v
1
,
y
1
= 1 + s
3
,
v
2
= 0.6 + y
2
+ s
2
+ s
3
,
s
1
= 0.6 −y
2
+ s
3
+ v
1
.
Associating the dual variables (0,−1,1) to the right-hand sides (1−x
1
,2 −x
2
,1),
one obtains the feasibility cut , x
2
−1 ≤ 0 , for the second branch. Thus, R = 2,
as the solutions in the two nodes satisfy the integrality requirement and are thus
7.6 Cuts Based on Branching in the Second Stage 329
terminal. The feasibility cut is thus that either x
1
−1 ≤ 0orx
2
−1 ≤ 0mustbe
satisfied. Because we also have x
1
≤2andx
2
≤ 2,wemaytake M
1
= M
2
= 1so
that we have to impose the following set of conditions:
x
1
≤ 2 −
δ
1
,
x
2
≤ 2 −
δ
2
,
δ
1
+
δ
2
≥ 1 ,
δ
1
,
δ
2
∈{0,1} .
b. Optimality cuts
We consider here a multicut approach,
θ
=
K
∑
k=1
θ
k
,
where, as usual, K denotes the cardinality of
Ξ
. We search for optimality cuts on a
given
θ
k
. Based on branching on the second-stage problem, one obtains a partition
of ℜ
n
2
+
into R terminal nodes Y
ρ
= {y |a
ρ
≤y ≤b
ρ
},
ρ
= 1,...,R . The objective
value of the second-stage program over Y
ρ
is
Q
ρ
(x
ν
,
ξ
k
)=min{q
T
y |Wy = h(
ξ
k
) −T(
ξ
k
)x
ν
, a
ρ
≤y ≤ b
ρ
} .
It is the solution of a linear program that by classical duality theory is also
Q
ρ
(x
ν
,
ξ
k
)=(
π
ρ
)
T
(h(
ξ
k
) −T(
ξ
k
)x
ν
)+(
π
ρ
)
T
a
ρ
+(
¯
π
ρ
)
T
b
ρ
} ,
where
π
ρ
,
π
ρ
,and
¯
π
ρ
are the dual variables associated with the original con-
straints, lower and upper bounds on y ∈Y
ρ
, respectively.
To simplify notation, we represent this expression as:
Q
ρ
(x
ν
,
ξ
k
)=(
σ
ρ
k
)
T
x
ν
+
τ
ρ
k
,
with (
σ
ρ
k
)
T
= −(
π
ρ
)
T
T(
ξ
k
) and
τ
ρ
k
=(
π
ρ
)
T
h(
ξ
k
)+(
π
ρ
)
T
a
ρ
+(
¯
π
ρ
)
T
b
ρ
.By
duality theory, we know that Q
ρ
(x,
ξ
k
) ≥ (
σ
ρ
k
)
T
x
ν
+
τ
ρ
k
. Moreover, Q(x,
ξ
k
)=
min
ρ
=1,...,R
Q
ρ
(x,
ξ
k
) . Thus,
θ
k
≥ p
k
( min
ρ
=1,...,R
(
σ
ρ
k
)
T
x
ν
+
τ
ρ
k
) . (6.2)
Note that some of the terminal nodes may be infeasible, in which case their dual
solutions contain unbounded rays with dual objective values going to ∞ so that the
minimum is in practice restricted to the feasible terminal nodes.
330 7 Stochastic Integer Programs
This expression takes the form of a Gomory function, as expected. Again, it un-
fortunately requires R extra binary variables to be included in a mixed integer linear
representation. This makes the branching on the second-stage very often computa-
tionaly unattractive.
Example 8
Consider the second-stage program
E
ξ
min{−8y
1
−9y
2
s. t. 3y
1
+ 2y
2
≤ ξ,−y
1
+ y
2
≤ x
1
,y
2
≤ x
2
,y ≥0, integer}.
Consider the value
ξ
1
= 8and ¯x =(0, 6)
T
. The optimal dictionary of the continu-
ous relaxation of the second-stage program is:
z = −136/5 + 17s
1
/5 + 11s
2
/5 ,
y
1
= 8/5 −s
1
/5 + 2s
2
/5 ,
y
2
= 8/5 −s
1
/5 −3s
2
/5 ,
s
3
= 22/5 + s
1
/5 + 3s
2
/5 ,
where s
1
, s
2
,and s
3
are the slack variables of the three constraints. Branching on
y
1
gives two nodes, y
1
≤1andy
1
≥2 , which turn out to be the only two terminal
nodes. For the first node, adding the constraint y
1
+ s
4
= 1 yields the following
dictionary after one dual iteration:
z = −17 + 9s
2
+ 17s
4
,
s
1
= 3 + 2s
2
+ 5s
4
,
y
2
= 1 −s
2
−s
4
,
s
3
= 5 + s
2
+ s
4
,
y
1
= 1 −s
4
.
We thus have dual variables (0, −9, 0) associated with the right-hand side (8, x
1
,x
2
)
of the constraints and −17 associated with the bound 1 on y
1
. Hence, Q
1
( ¯x,8)=
−9x
1
−17 .
Similarly, we add y
1
−s
4
= 2 for the second node. We obtain:
z = −25 + 9/2s
1
+ 11/2s
4
,
y
1
= 2 + s
4
,
y
2
= 1 −s
1
/2 −3/2s
4
,
s
3
= 5 + s
1
/2 + 3/2s
4
,
s
2
= 1 + s
1
/2 + 5/2s
4
.
7.7 Extensive Forms and Decomposition 331
We now have dual variables, (−9/2,0,0) , associated with the right-hand side
(8,x
1
,x
2
) of the constraints and 11/2 associated with the lower bound 2 on y
1
.
Hence, Q
2
( ¯x,8)=−25 . Applying (6.2), we conclude that
θ
1
≥ p
1
min(−9x
1
−17,−25) , (6.3)
where p
1
is the probability of ξ =
ξ
1
.
Exercises
1. Consider Example 7. We have see that x ∈K
2
(1) if x
1
≤ 2, x
2
≤ 2 and either
x
1
≤ 1orx
2
≤ 1 . Thus, the feasibility set is the union of two sets.
Apply Proposition 11 in two cases:
(a) if x =(2, 2)
T
;
(b) if x =(1.4,1.6)
T
.
• Show that the disjunctive cut formed in (a) is the same as the continuous
induced cut: x
1
+ x
2
≤ 3 . (This example can be found in Section 7.8b.)
• Show that no violated disjunctive cut is obtained in (b).
2. Consider Example 8.
(a) Compare the cut (6.3) with the one obtained by L -shaped cut for
ξ
1
= 8.
Show that (6.3) is stronger for x
1
≤1.5.
(b) Assume 2x
1
+ x
2
≤ 6 . Convexifying (6.3)over 2x
1
+ x
2
≤ 6, x
1
≥ 0,
x
2
≥ 0 gives a line passing by (0,− 25p
1
) and (3, −44p
1
) in the (x
1
,
θ
1
)
space, namely
θ
1
≥ p
1
(−25−
19
3
x
1
) . This convexification is stronger that
the L -shaped cut only for x
1
≤ 33/62 .
7.7 Extensive Forms and Decomposition
Problems with mixed integer second-stage can sometimes be solved by decom-
posing the second-stage variables into their discrete parts and continuous parts.
Assuming a mixed second stage with binary variables, one can divide y(
ω
)
T
=
(y
B
(
ω
)
T
,y
C
(
ω
)
T
) where y
B
(
ω
) is the vector of binary variables and y
C
(
ω
) the
vector of continuous variables. Partitioning q and W in a similar fashion, the clas-
sical two-stage program becomes
min z = c
T
x + E
ξ
q
T
B
(
ω
)y
B
(
ω
)+E
ξ
Q(x,y
B
(
ω
),
ω
)
s. t. Ax = b ,
x ∈X , y
B
(
ω
) ∈Y
B
(
ω
) ,
332 7 Stochastic Integer Programs
where
Q(x,y
B
(
ω
),
ω
)=min{q
T
C
(
ω
)y
C
(
ω
)
s. t. W
C
y
C
(
ω
) ≤ h(
ω
) −T(
ω
)x −W
B
y
B
(
ω
),y
C
(
ω
) ∈Y
C
(
ω
)} .
When ξ is a discrete random variable, this amounts to writing down the extensive
form for the second-stage binary variables. When the number of realizations of ξ
remains low, such a program is still solvable by the ordinary L -shaped method. An
extension of this idea to a three-stage problem in the case of acquisition of resources
can be found in Bienstock and Shapiro [1988].
The same idea applies for multistage stochastic programs having the block sepa-
rable property defined in Section 3.4, provided the discrete variables correspond to
the aggregate level decisions and the continuous variables correspond to the detailed
level decisions. Then the multistage program is equivalent to a two-stage stochastic
program, where the first stage is the extensive form of the aggregate level problems
and the value function of the second stage for one realization of the random vector
is the sum, weighted by the appropriate probabilities of the detailed level recourse
functions for that realization and all its successors. This result is detailed in Lou-
veaux [1986], where examples are provided.
Example 9
As an illustration, consider the warehouse location problem similar to those studied
in Section 2.4. As usual, let
x
j
=
1ifplantj is open,
0otherwise,
with fixed-cost c
j
,and v
j
, the size of plant j , with unit investment cost g
j
,be
the first-stage decision variables. Assume k = 1,...,K realizations of the demands
d
k
i
in the second stage. Let y
k
ij
be the fraction of demand d
k
i
served from j , with
unit revenue q
ij
(see Section 2.4c. Now, assume the possibility exists in the second
stage to extend open plants by an extra capacity (size) of fixed value e
j
at cost
r
j
. For simplicity, assume this extension can be made immediately available (zero
construction delay).
To this end, let
w
k
j
=
⎧
⎪
⎨
⎪
⎩
1 if extra capacity is added to j
when the second-stage realization is k,
0otherwise.
The two-stage stochastic program would normally read as
7.7 Extensive Forms and Decomposition 333
max−
n
∑
j= 1
c
j
x
j
−
n
∑
j= 1
g
j
v
j
+
K
∑
k=1
p
k
max
m
∑
i=1
n
∑
j= 1
q
ij
y
k
ij
−
n
∑
j= 1
r
j
w
k
j
s. t.
n
∑
j= 1
y
k
ij
≤ 1 , k = 1,...,K , i = 1,...,m ,
x
j
∈{0,1} , v
j
≥ 0 , j = 1,...,n ,
m
∑
i=1
d
k
i
y
k
ij
−e
j
w
k
j
≤ v
j
, k = 1,...,K , j = 1,...,n ,
0 ≤ y
k
ij
≤ x
j
, i = 1,...,m , j = 1...,n ,
k = 1,...,K ,
w
k
j
≤ x
j
, j = 1,...,n , k = 1,...,K ,
w
k
j
∈{0,1} , j = 1,...,n , k = 1,...,K .
Using the extensive form for the binary variables, w
k
j
s transforms it into
max−
n
∑
j= 1
c
j
x
j
−
n
∑
j= 1
g
j
v
j
−
n
∑
j= 1
K
∑
k=1
p
k
r
j
w
k
j
+
K
∑
k=1
p
k
max
n
∑
i=1
n
∑
j= 1
q
ij
y
k
ij
s. t. x
j
∈{0, 1} , v
j
≥ 0 , j = 1,...,n ,
n
∑
j= 1
y
k
ij
≤ 1 , i = 1,...,m , k = 1,...,K ,
w
k
j
≤ x
j
,
m
∑
i=1
d
k
i
y
k
ij
≤ v
j
+ e
j
w
k
j
, j = 1,...,n ,
k = 1,...,K ,
w
k
j
∈{0, 1} , 0 ≤ y
k
ij
≤ x
j
, i = 1,...,m ,
j = 1,...,n , k = 1,...,K .
Thus, at the price of expanding the first-stage program, one obtains a second stage
that enjoys the good properties of continuous programs.
When the stochastic programs with mixed-integer second-stage cannot be effi-
ciently decomposed as above, then it can be solved through a scenario decompo-
sition approach. In this method, the nonanticipativity constraints are subjected to
Lagrangian relaxation to create mixed-integer programs which are separable in the
realizations of the random vector. Details on the method can be found in Carøe and
Schultz [1999].