Geoscience Reference
In-Depth Information
(a)
Z.S/
C
Z.T/
Z.S
[
T/
C
Z.S
\
T/;
8
S;T
N
.
(b)
Z.S
[f
i
g
/
Z.S/
Z.T
[f
i
g
/
Z.T/;
8
S
T
N
and
i
2
N
.
(c) If, in addition,
Z
is non-increasing, then
Z.T/
Z.S/
C
P
i2T nS
i
.S/
,
8
S;T
I
.
In the following we suppose that N is the set of potential facilities, i.e. N
D
I,
and we consider as set function Z the cost function of UFLP solutions. That is
Z.S/
D
P
i2S
f
i
C
P
j2J
min
i2I
c
ij
. To see that Z.:/ is supermodular we recall
that a positive linear combination of supermodular functions is supermodular and
we observe that Z.S/
D
f.S/
C
c.S/ with f.S/
D
P
i2S
f
i
and c.S/
D
P
j2J
min
i2I
c
ij
. Thus, it is enough to see that both f.:/and c.:/ are supermodular.
Because f.S/is linear, it is clear that it is supermodular. We next see that c.:/ is
also supermodular.
Proposition 3.2
c.:/
is supermodular and non-increasing.
Proof
We will use the characterization of supermodular functions of Lemma
3.1
b.
For S
T
I,andi
2
I
n
T ,
i
0
2S
c
i
0
j
D
X
j2J
min
0;c
ij
min
i
0
2S
c
i
0
j
c.S
[f
i
g
/
c.S/
D
X
j2J
min
i
0
2S[fig
c
i
0
j
min
min
0;c
ij
min
i
0
2T
c
i
0
j
D
X
j2J
c
i
0
j
D
X
min
i
0
2T [fig
c
i
0
j
min
i
0
2T
j2J
c.T
[f
i
g
/
c.T/;
where the inequality follows since min
i
0
2S
c
i
0
j
min
i
0
2T
c
i
0
j
for all j
2
J.
Furthermore, c is non-increasing since
min
i
0
2S[fig
c
i
0
j
0:
c.S
[f
i
g
/
c.S/
D
X
j2J
c
i
0
j
min
i
0
2S
For the function c.:/ the incremental value of adding element i to the set S is
c.S
[f
i
g
/
c.S/. Hence, statement (b) of Lemma
3.1
can be rewritten as
c.T/
c.S/
C
X
i
Œc.S
[f
i
g
/
c.S/
D
c.S/
C
X
i
Œc.S
[f
i
g
/
c.S/;
8
S;T
I:
2
T
n
S
2
T
n
S
(3.47)
The UFLP formulation below exploits the supermodular property of
z
.:/ and c.:/
as well as the non-increasing property of c.:/. Consider the polyhedron
