Geoscience Reference
In-Depth Information
interested reader is referred to Krarup and Pruzan (
1983
), Cornuéjols et al. (
1990
),
Labbé et al. (
1995
), ReVelle and Laporte (
1996
)orVerter(
2011
) for overviews of
the main contributions.
3.4.1
Bounds for UFLP Derived from LP Duality
Consider the LP relaxation of UFLP, in which constraints (
3.38
) have been
written as y
i
x
ij
0, and the upper bound constraints on the y variables
as
y
i
1, i
2
I.Let
u
,
w
and t denote the vectors of dual variables of
appropriate dimensions associated with constraints (
3.37
), (
3.38
) and the upper
bound constraints, respectively. Then, the dual of the LP relaxation of UFLP is
maximize
X
j2J
u
j
X
i2I
DUFLP
t
i
(3.41)
subject to
X
j2J
w
ij
t
i
f
i
i
2
I
(3.42)
u
j
w
ij
c
ij
i
2
I;j
2
J
(3.43)
w
ij
0
i
2
I; j
2
J
(3.44)
t
i
0
i
2
I:
(3.45)
The optimal values for the t variables can be determined from the optimal
w
values as t
i
D
P
j2J
w
ij
f
i
C
, i
2
I,where.a/
C
D
max
f
0;a
g
. In turn, the
optimal
w
values can be determined from the optimal
u
values as
w
ij
D
u
j
c
ij
C
,
i
2
I;j
2
J. Therefore, DUFLP can be expressed in terms of only
u
variables as
0
@
X
j2J
1
C
max D.
u
/
D
X
j2J
u
j
X
i2I
u
j
c
ij
C
f
i
A
DUFLP
:
Furthermore, the following optimality conditions hold:
(a) There exists an optimal DUFLP solution where
u
j
min
i2I
c
ij
for all j
2
J.
If
u
j
< min
i2I
c
ij
for some j
2
J, then we can increase the value of
u
j
without
decreasing the objective function value.
(b) There exists an optimal DUFLP solution where
P
j2J
u
j
c
ij
C
f
i
0 for
all i
2
I.
If
P
j2J
u
j
c
ij
C
f
i
>0for some i
2
I, we can decrease the value of
some component
u
j
(with
u
j
>c
ij
/ without decreasing the objective function
value.
