Geoscience Reference
In-Depth Information
To illustrate the second strategy let
u
be a dual solution satisfying the optimality
condition (b) above and define I.
u
/
Df
i
2
I
j
P
j2J
.c
ij
u
j
/
C
f
i
D
0
g
. Assume
further that
u
j
min
i2I.
u
/
c
ij
. Consider now a set of facilities S.
u
/
I.
u
/ satisfying
max
i2I.
u
/
c
ij
D
max
i2S.
u
/
c
ij
,foralli
2
I and let s
j
Df
i
2
S.
u
/
j
c
ij
<
u
j
g
, j
2
J.
Then, D.
u
/
D
Z.S.
u
// (see Proposition 3.2. in Cornuéjols et al.
1990
). This means
that under the above assumptions, S.
u
/ is an optimal UFLP solution.
Note that D.
u
/
D
Z.S.
u
// means that the optimal UFLP value coincides with
that of its LP relaxation. Thus, in general, one should not expect to find a solution
u
that together with S.
u
/ satisfies the conditions stated above. However the DUALOC
heuristic (see Erlenkotter
1978
; Bilde and Krarup
1977
), which follows this spirit
has proved to be extremely effective for finding optimal or near-optimal solutions
for the UFLP. The basic idea is to start with
u
D
.
u
j
/
j2J
D
.min
i2I
c
ij
/
j2J
,andthen
progressively attempt to increase each component
u
j
while satisfying condition (b).
If
u
j
can be increased, then its next value is min
f
c
ij
j
c
ij
>
u
j
g
, provided that this
value satisfies (b). If not,
u
j
is increased to the maximum possible value. Indeed,
the outcome of the above heuristic depends on the order in which the indices in
j
2
J are considered. Necessary and sufficient conditions for the duality LP gap to
be zero, which may lead to tighter bounds have been proposed in Mladenovi´cetal.
(
2006
). Heuristics in the same spirit have been proposed for other discrete facility
location problems, like the one for the stochastic version of the FLP proposed in
Louveaux and Peeters (
1992
).
3.4.2
The UFLP as the Optimization of a Supermodular
Set Function
As mentioned, the UFLP can be stated as the minimization of a set function. In
this section we see that an alternative formulation for the UFLP can be obtained
by exploiting the supermodularity property of this set function, which has been
observed by several authors, namely Spielberg (
1969a
), Frieze (
1974
), Babayev
(
1974
), Fisher et al. (
1978
), and we relate such a formulation with a radius based
formulation. We start by recalling some well-known results on supermodular set
functions (see, e.g., Section III.3.1 in Nemhauser and Wolsey
1988
) and introduce
some additional notation.
Definition 3.1
Let N be a finite set, and Z a real-valued function on the subsets
of N. The function Z is
supermodular
if Z.S/
C
Z.T/
Z.S
[
T/
C
Z.S
\
T/;
8
S;T
N.
For i
2
N let
i
.S/
D
Z.S
[f
i
g
/
Z.S/ be the
incremental value
of adding
element i to the set S.
Lemma 3.1
Each of the following statements is equivalent and defines a super-
modular set function.
