Geoscience Reference
In-Depth Information
In order to minimize the ordered median function for a given set of nonnegative
lambda parameters
1
;:::;
n
, we define the following problem.
X
n
minimize
j
j
(10.5)
jD1
subject to .1
z
ij
/M
C
j
w
i
h
e
g
;x
a
i
i
; for e
g
2
B
o
;i;j
D
1;2;:::;n
(10.6)
n
X
z
ij
D
1; for j
D
1;:::;n
(10.7)
iD1
n
X
z
ij
D
1; for i
D
1;:::;n
(10.8)
jD1
j
jC1
; for j
D
1;:::;n
1
(10.9)
j
0;
for j
D
1;:::;n
(10.10)
z
ij
2f
0;1
g
; for i;j
D
1;:::;n
(10.11)
d
:
x
2
R
(10.12)
Constraints (
10.7
)and(
10.8
) define a permutation by placing at each position
a single distance to a facility and each distance to a facility at a single sorted
position. Constraints (
10.6
) relate distance values with the values placed in a
sorted sequence. Constraint (
10.9
) imposes that the sorted values are ordered non-
increasingly. Finally, (
10.10
)-(
10.12
) define the range of variables of the model.
The above approach solves efficiently the problem in any dimension provided
that the gauges used to measure distances are polyhedral since problem (
10.5
)-
(
10.12
) is a MILP that can be handled with any of the nowadays available MIP
solvers.
We would like to conclude this section with some comments on several exten-
sions of the considered problem. On the one hand, the multicriteria planar version
of the above problem was analyzed in Nickel et al. (
2005
). On the other hand,
the planar case of the ordered median problem using a `
p
-norm was also studied
by Drezner and Nickel (
2009a
,
b
) where techniques of global optimization were
used for solving it. In addition, Espejo et al. (
2009
), Rodríguez-Chía et al. (
2010
)
proposed an adaptation of the Weiszfeld algorithm for the convex version of this
problem, i.e., 0
1
:::
n
. Finally, we would like to mention some
references that consider the multifacility version of particular classes of ordered
median problems. These references can be seen as a starting point to dig into this
challenging topic. The interested reader is referred to Blanco et al. (
2014b
), Ben-
Israel and Iyigun (
2010
), Brimberg et al. (
2000
), Schöbel and Scholz (
2010
)for
different approaches to the continuous multifacility location problem.