Geoscience Reference
In-Depth Information
<
:
=
;
.;x;y/
2 RB
jIjjJj
B
jIj
W
X
i2S
f
i
y
i
C
c.S/
C
X
i…S
P
SF
D
i
.S/y
i
;
8
S
I
;
B
jJj
are the domains of the binary
vectors associated with the location and allocation variables x and y, respectively.
Theorem 3.1
Let
T
I
and
.;x
T
;y
T
/
2
B
jIjjJj
and
where is a continuous variable and
B
jIj
, with
x
and
y
the incidence vectors of the UFLP solution associated with subset
T
. Then,
.;x
T
;y
T
/
2
P
SF
if and only if
Z.T/
.
Proof
If .;x
T
;y
T
/
2
P
SF
then
X
i2T
B
jIjjJj
R
f
i
y
i
C
c.T/
C
X
i…T
i
.T/y
i
D
X
i2T
f
i
C
c.T/
D
Z.T/:
Suppose now that
Z.T/.Wehave
f.T/
D
X
i2T
f
i
y
i
D
X
i2T \S
f
i
y
i
C
X
i2T nS
f
i
y
i
D
X
i2S
f
i
y
i
C
X
i2T nS
f
i
y
i
;
for all S
I:
Since c is non-increasing supermodular, by (
3.47
), we also have
c.T/
c.S/
C
X
i2T nS
h
c.S
[f
i
g
/
c.S/
i
D
c.S/
C
X
i…S
h
c.S
[f
i
g
/
c.S/
i
y
i
;
for all S
I:
Thus, for all S
I
h
c.S
[f
i
g
/
c.S/
i
y
i
:
Z.T/
D
f.T/
C
c.T/
X
i
f
i
y
i
C
X
i
f
i
y
i
C
c.S/
C
X
i
2
S
2
T
n
S
…
S
Hence,
Z.T/
X
i2S
f
i
y
i
C
c.S/
C
X
i…S
i
.S/y
i
; for all S
I.
Therefore, .;y
T
;x
T
/
2
P
SF
and the result follows.
As a consequence of Theorem
3.1
, the UFLP can be stated as the following MIP
(see Nemhauser and Wolsey
1981
):
minimize
(3.48)
X
i2I
f
i
y
i
C
c.S/
C
X
e…S
i
.S/y
i
8
S
I
subject to
(3.49)
