Geoscience Reference
In-Depth Information
latter arises from the fact that it is particularly suited for the application of a dual-
based heuristic, which is a popular method for obtaining sharp lower and upper
bounds for discrete facility location problems. This fact was explored by Van Roy
and Erlenkotter (
1982
). Multiplying constraints (
11.43
)by
1 the dual of the linear
relaxation of model (
11.41
)-(
11.45
) becomes:
Maximize
X
t2T
X
v
jt
(11.46)
j2J
subject to v
jt
w
ijt
c
ijt
; t
2
T; i
2
I; j
2
J
(11.47)
X
X
w
ij
F
it
; t
2
T; i
2
I
(11.48)
j2J
2T
it
w
ijt
0; t
2
T; i
2
I; j
2
J:
(11.49)
In this model, v
jt
and
w
ijt
(t
2
T , i
2
I, j
2
J) are the dual variables associated with
constraints (
11.42
)and(
11.43
), respectively (with the latter previously multiplied
by
1). The set T
it
(i
2
I, t
2
T ) contains the operating periods for facility i if
a change (installation or removal) occurs in this location in period t. In particular,
T
it
Df
1;:::;t
g
if i
2
I
c
and T
it
Df
t;:::;
j
T
jg
if i
2
I
o
.
From (
11.47
)and(
11.49
)wemayset
w
ijt
D
max
f
0;v
jt
c
ijt
g
; t
2
T; i
2
I; j
2
J;
which yields the following condensed dual:
Maximize (
11.46
)
subject to
X
j2J
X
max
f
0;v
jt
c
ijt
g
F
it
; t
2
T; i
2
I:
(11.50)
2T
it
The complementary slackness conditions for the linear relaxation of model
(
11.41
)-(
11.45
) are the following:
X
x
ijt
1
!
D
0
v
jt
t
2
T; j
2
J
i2I
0
@
X
1
A
D
0; t
2
T; i
2
I; j
2
J
w
ijt
z
i
x
ijt
2T
it
x
ijt
v
jt
c
ijt
w
ijt
D
0; t
2
T; i
2
I; j
2
J
z
it
S
it
D
0;
t
2
T; i
2
I;
where S
it
represent the slack variables for constraints (
11.50
).
