Geoscience Reference
In-Depth Information
A constant
P
j2J
g
j1
must be added to the objective to get the right optimal
value. This way, when variable
w
j1
takes value one, j is covered and the penalty
cost
g
j1
is removed from the objective function.
Minimum Cost Maximal Covering Problem (MCMCP): This is the name for the
model introduced in Broin and Lowe (
1986
) whose only difference with regard
to CP is that the total number of facilities is limited. They gave a dynamic
programming algorithm for solving MCMCP in O.p
2
n min
f
m
2
;n
2
g
/ time when
the matrix A
D
.a
ij
/ is totally balanced.
p-Median Problem: Studied in detail in Chap. 2, the p-Median Problem (pMP)
consists in, given a set of n demand points, choosing p of them to locate facilities
and allocating each demand point to one of these facilities (which receive the
name of medians) in such a way that the total cost be minimum, where the cost of
allocating j to i is the distance d
ij
between the two points (assuming d
ii
D
0
8
i
and d
ij
>0in all other cases).
Instead of using the classical formulation for pMP, an artificial set J can be
designed in order to get it as a particular case of (COV): for each demand point j,
a vector D
j
D
.D
1j
;:::;D
G
j
j
/ which is obtained by sorting in increasing order
the values in
f
d
1j
;:::;d
nj
g
(removing multiplicities):
0
D
D
1j
<D
2j
<:::<D
G
j
j
D
max
1in
f
d
ij
g
:
Then define J
Df
.`;j/
W
j
2f
1;:::;n
g
;`
2f
2;:::;G
j
gg
and a
i;.`;j/
D
1 if and only if d
ij
<D
`j
. Besides, we set f
i
D
0
8
i
2
I, e
i
D
1
8
i
2
I, b
.j;`/
D
0
8
.`;j/
2
J,andh
D
p. Coefficients g
.`;j/1
are defined with
value D
`1;j
D
`j
and g
.`;j/k
D
0
8
k
2.
With this approach, constraints (
5.3
) force variables
w
.j;`/1
to take value zero
if there is no open facility at a distance less than D
`j
from demand point j
and the allocation cost of j is increased from D
`1;j
to D
`j
, as desired. A
constant
P
jD1
D
G
j
j
must be added to the objective function to get the right
optimal value. This formulation has been very successfully used in García et al.
(
2011
), where a column-and-row generation algorithm is developed to solve very
large instances.
Uncapacitated Facility Location Problem: The problem considered in Chap.
3
(UFLP) and pMP differ in the number of centers which in UFLP is not fixed
beforehand, but there is a fixed cost f
i
for opening a facility at site i. Therefore,
a straightforward modification of these parameters will allow to obtain UFLP
as a particular case of (COV). This particular formulation was first proposed
in Cornuéjols et al. (
1980
) and later in Kolen and Tamir (
1990
).
Tab le
5.1
summarizes the information about covering models in the literature
which have been shown in this chapter to be particular cases of (COV).
