Geoscience Reference
In-Depth Information
A second family of (binary) variables is
w
jk
. Here, j belongs to the set of demand
points J while k belongs to an index set K
Df
1;:::;h
g
, whose meaning will
depend on the particular model that is considered. Associated to variables
w
jk
,fixed
costs g
jk
2
are given. These costs g
jk
can be negative, representing in this case
the profit from
w
jk
taking value one. In order to avoid unnecessary complicating
constraints in the basic model, without loss of generality, we assume that g
j1
g
j2
:::
g
jh
for each j
2
J. Whenever this condition does not hold, it will be
explicitly stated.
The mathematical Integer Programming formulation for our general covering
model is:
R
(COV) Minimize
X
i2I
f
i
y
i
C
X
j2J
X
g
jk
w
jk
(5.1)
k2K
subject to
X
i2I
y
i
p;
(5.2)
X
a
ij
y
i
D
b
j
C
X
k2K
w
jk
8
j
2
J;
(5.3)
i2I
y
i
2f
0;1;:::;e
i
g
i
2
I;
(5.4)
w
jk
2f
0;1
g
j
2
J;
8
k
2
K:
(5.5)
The objective function (
5.1
) has two parts. The first sum returns the total fixed
cost of opening y
i
facilities at site i
2
I. The second sum returns the total cost (or
profit, if negative) provided by the
w
-variables that take value one. Constraint (
5.2
)
limits the number of centers to p. Note that all the centers installed at the same site
contribute to the sum.
The main constraints in the model are (
5.3
). For each demand point j
2
J,the
left-hand side of (
5.3
) measures the number of open facilities which are covering j.
This number must be at least equal to the lower bound b
j
on the right-hand side,
while the sum of
w
jk
variables measures the slack in the coverage of j, i.e., the
number of centers which are covering j besides the minimum number b
j
.Dueto
the condition that we imposed on the g-values, the
w
-variables taking value one will
be in the first positions, that is, constraints
w
jk
w
j;kC1
, j
2
J, k
2f
1;:::;h
1
g
are satisfied without including them explicitly in the formulation. In such a way,
acostg
j1
will be paid if demand point j is covered by at least b
j
C
1 centers;
additional cost g
j2
will be paid if demand point j is covered by at least b
j
C
2 centers
and so on.
Constraints (
5.4
) are the integrality constraints for y-variables and impose that at
most e
i
centers can be installed at site i. Constraints (
5.5
) state that variables
w
are
binary.
Therefore, model (COV) forces to cover each demand point j with a minimum
of b
j
facilities by using at most p facilities while minimizing the location cost of the
facilities plus an additional cost (or, instead, minus an additional benefit) associated
to the number of facilities which over-cover customers. By giving particular values
