Information Technology Reference
In-Depth Information
are supply nodes with a supply of z i ( y i
δ i ); node n is a supply node with
supply
j
p j
z i ( y i
δ i ). The nodes in J are demand nodes, each with
J
i
I
demand p j . I 2 are transshipment nodes. The arc ( n,i ) has a cost of H i while
arc ( i,k )
I 2 has a cost of T ik . As noted in Subsection 4.1, the solution to
this min-cost network flow problem gives the minimum recovery cost given the
initial preparedness decisions and the damage incurred in Level 2.
By considering the dual of this network flow problem, we note that R ( x, y, z ; δ )
is a linear function of z
I 1 ×
δ ). Specifically, let α i be the dual variable corre-
sponding to the flow balance constraint for supply node i
·
( y
I 1 , β j be the dual
variable corresponding to the flow balance constraint of demand node j
J ,
and let α 0 be the dual variable for the supply node n . Therefore,
R ( x, y, z ; δ )=
i∈I
( α i
α 0 ) z i ( y i
δ i )
( β j
α 0 ) p j .
(24)
j∈J
Without loss of generally, we can set α 0 = 0, since one of the flow-balance
constraints is redundant in a network flow problem. We note that R ( x, y, z ; δ ),
unfortunately, is not linear in the decision variables of ( L1 ).
5.2 An Iterative Solution Approach
Our iterative approach begins with solving a relaxation of ( M ) which ignores con-
straints (23), and then successively refines this relaxation by adding
constraints (23) with the righthand side written as a function of ( x, y, z ).
We define the following Restricted Master Problem :
x,y,z ; π
i∈I
( RM ):
min
( f i y i + h i z i )+ π
subject to
i∈I
y i
E,
(25)
x ij
=1
j
J,
(26)
i
I
d ij x ij
my i
i
I,j
J,
(27)
z i
C i y i
i
I,
(28)
p j x ij
z i
i
I,
(29)
j
J
y i ,x ij
∈{
0 , 1
}∀
i
I,j
J,
(30)
z i
0
i
I,
(31)
α i z i ( y i
β j p j , δ
π
δ i )
∈D
.
(32)
i∈I
j∈J
In the dual ascent approach we propose here, constraints (32) are to be gener-
ated iteratively given each set of values ( x, y, z ) considered. The set
D
contains
 
Search WWH ::




Custom Search