Geoscience Reference
In-Depth Information
Condition (b) means that the objective function value of an optimal dual solution
reduces to
P
j2J
u
j
. In other words, an optimal dual solution exists with t
i
D
0 for
all i
2
I. Hence, the complementarity slackness conditions for constraints (
3.42
)are
0
@
f
i
X
j2J
1
u
j
c
ij
C
A
y
i
D
0
i
2
I:
(3.46)
These conditions, which apply to any primal-dual optimal pair to the LP relax-
ation of UFLP, hold trivially for all i
2
I with y
i
D
0.Wheny
i
>0,(
3.46
) holds
provided that
P
j2J
u
j
c
ij
C
D
f
i
. For the integer UFLP the complementarity
slackness conditions (
3.46
) give the guidelines for primal-dual heuristics. Two
alternative strategies may be applied: (1) the primal solution is obtained first and
then a vector
u
is built to satisfy
P
j2J
u
j
c
ij
C
D
f
i
for all i
2
I with
y
i
D
1; or (2) the dual solution
u
is first obtained and then the primal solution sets
y
i
D
1 for all i
2
I with
P
j2J
u
j
c
ij
C
D
f
i
. The first strategy can be applied
starting from any set of open facilities S (which can be obtained, for instance, with
a greedy heuristic). The associated dual solution
u
.S/ can be obtained by setting
u
j
.S/
D
min
i2S
c
ij
for all j
2
J (note that this solution need not satisfy condition
(b)). The DUFLP objective function value for
u
j
.S/ is
0
@
X
j2J
1
C
D.
u
.S//
D
X
j2J
u
j
.S/
X
i2I
u
j
.S/
c
ij
C
f
i
A
D
0
@
X
j2J
1
C
min
i
0
2S
c
i
0
j
c
ij
C
f
i
X
i
0
2S
c
i
0
j
X
i2I
A
min
D
j2J
0
@
X
j2J
1
C
min
i
0
2S
c
i
0
j
c
ij
C
f
i
X
i
0
2S
c
i
0
j
X
i…S
A
min
:
j2J
Since the value of the primal solution associated with S is Z.S/
D
P
i2S
f
i
C
P
j2J
min
i2S
c
ij
, the deviation between the primal/dual values of S and
u
.S/ is
0
@
X
j2J
1
C
min
i
0
2S
c
i
0
j
c
ij
C
f
i
Z.S/
D.
u
.S//
D
X
i2S
f
i
C
X
i…S
A
:
The above expression for the deviation suggests choosing S in order to satisfy
P
j2J
min
i
0
2S
c
i
0
j
c
ij
C
f
i
0 for all i
…
S, since in this case the above
deviation reduces to
P
i2S
f
i
.
