Geoscience Reference
In-Depth Information
0
(3.50)
y
i
2f
0;1
g
i
2
I;
(3.51)
where I
D
I
[f
i
g
and i
is a fictitious facility such that (1) c
i
k
> max
i2I
c
ij
,
for all j
2
J;and(2)
P
j2J
c
ij
> max
i2I
.f
i
C
P
j2J
c
ij
/. This assumption
guarantees that at least one variable y
i
is at value one in any optimal solution to the
above formulation.
Taking into account the supermodularity of c.:/ we can obtain a tighter formula-
tion by respectively substituting objective (
3.48
) and constraints (
3.49
)by
minimize
X
i2I
f
i
y
i
C
X
j2J
j
;
(3.52)
min
i
0
2S[fig
i
0
2S
c
i
0
j
y
i
;
8
S
I
;j
2
J:
i2S
c
ij
C
X
i…S
j
min
and
c
i
0
j
min
(3.53)
The following observation indicates that only a polynomial number of con-
straints (
3.53
) is required to obtain a valid formulation for the UFLP.
Remark 3.1
For S
I and j
2
J given, the right-hand side of their associated
constraint (
3.53
) does not change if the summation is taken over all i
2
I,since
min
i
0
2S[fig
c
i
0
j
min
i
0
2S
c
i
0
j
D
0,fori
2
S. Moreover, for any S
I,thevalue
of min
i2S
c
ij
will be one of the values c
ij
, with i
2
S.Thatis,foranyS its associated
constraint (
3.53
) can be written as
j
c
sj
C
X
i2I
.c
ij
c
sj
/
y
i
;
for some s
2
S:
To apply the above remark and obtain a formulation with a polynomial number
of constraints, for each j
2
J,weordertheelementsofI in non-decreasing values
of their coefficients c
ij
, and we denote by i
r
the rth index according to that ordering.
That is, c
i
1
j
c
i
2
j
:::
c
i
m
j
c
i
mC1
j
,wherec
i
mC1
j
D
c
i
j
is the allocation
cost of customer j to the fictitious facility i
.
Theorem 3.2
The UFLP can be formulated as
.
SUFLP
/v
S
D
minimize
X
i
f
i
y
i
C
X
j
j
(3.54)
2
I
2
J
subject to
j
c
i
r
j
C
X
i
.c
ij
c
i
r
j
/
N
y
i
r
D
1;:::;m
C
1; j
2
J
2
I
(3.55)
j
0
(3.56)
j
2
J
y
i
2f
0;1
g
i
2
I:
(3.57)
