Geoscience Reference
In-Depth Information
X
n
X
n
x
ij
D
1;
8
k
D
1;:::;n
(10.35)
iD1
jD1
n
n
X
X
a
i
x
ij
b
j
y
j
;
8
j
D
1;:::;n;
(10.36)
iD1
kD1
X
n
y
j
D
p;
(10.37)
jD1
X
n
X
n
X
n
X
n
c
ij
x
ij
c
ij
x
kC1
;
8
k
D
1;:::;n
1; (10.38)
ij
iD1
jD1
iD1
jD1
x
ij
2f
0;1
g
;
8
i;j;k
D
1;:::;n;
(10.39)
y
j
2f
0;1
g
;
8
j
D
1;:::;n:
(10.40)
The objective function accounts for the weighted sum of the transportation cost
using the lambda parameters. Constraints (
10.34
) ensure that each origin site i is
allocated exactly to one server j. Constraints (
10.35
) guarantee that any position
in the sorted vector of
client-server
costs is allocated to just one pair. Constraints
(
10.36
) are the capacities constraint and also ensure that one origin may be allocated
to a specific server only if it is open. Constraint (
10.37
) fixes the number of facilities
to be located. Finally, constraints (
10.38
) ensure that the transportation cost assigned
to the k-position is smaller than the one assigned to the .k
C
1/-position.
10.5.2
A Covering Formulation and Some Properties
In this subsection, we introduce a formulation for the binary assignment capacitated
discrete ordered median problem based on covering variables. This formulation was
first presented in Puerto (
2008
).
We first define G as the number of different non-zero elements of the cost matrix
C. Hence, we can order the different values of C in non-decreasing sequence:
c
.0/
WD
0<c
.1/
<c
.2/
<
<c
.G/
WD
max
1i;jn
f
c
ij
g
:
Given a feasible solution, we can use this ordering to perform the sorting process
of the allocation costs. This can be done by the following variables (j
D
1;:::;n
and k
D
1;:::;G):
u
jk
WD
(
1; if the j-th smallest allocation cost is at least c
.k/
,
0; otherwise.
(10.41)
With respect to this definition the j-th smallest cost element is equal to c
.k/
if
and only if
u
jk
D
1 and
u
j;kC1
D
0. Therefore, we can reformulate the objective
