Geoscience Reference
In-Depth Information
minimize
P
iD1
i
z
i
subject to
w
i
h
e
g
;x
a
i
i
z
i
;e
g
2
B
o
;i
D
1;2;:::;n
z
i
z
iC1
;
(P
)
i
D
1;2;:::;n
1
where e
g
are the extreme points of B
0
.
Lemma 10.2
Let
X
be an optimal solution of
P
.
(i) If
X
2
O
then
X
is also an optimal solution to the ordered median problem
constrained to
O
.
(ii) If
X
2
O
0
ยค
O
then the optimal solution of the ordered median problem
constrained to
O
0
is better than the optimal solution of the ordered median
problem constrained to
O
.
Proof
(i) At an optimal point X
in O
we have
w
i
h
e
g
i
;X
a
i
iD
z
i
;i
D
1;2;:::;n; for some g
i
;
which means that
z
i
D
w
i
.X
a
i
/ and the result follows.
(ii) At an optimal point X
of P
in O
0
we have
h
e
g
;X
a
i
i
<
z
i
for all g
for at least one i. This means that we can decrease the objective function by
moving from O
to O
0
and the result follows.
Based on Lemma
10.2
we develop a another algorithm for this problem. For each
ordered region we solve the problem as a linear program which geometrically means
either finding the locally best solution in this ordered region or finding out that this
region does not contain the global optimum by Lemma
10.2
. In the former case
two situations may occur. First, if the solution lies in the interior of the considered
region (in
n
) then we move to a different one not yet processed and secondly, if
the solution is on the boundary we do a local search in the neighborhood regions
where this point belongs to. It is worth noting that to accomplish this search a list
L
R
containing the already visited neighborhood regions is used in the algorithm.
Besides, it is also important to realize that neither Step 2 nor Step 5 need to explicitly
construct the corresponding ordered region. It suffices to evaluate and to sort the
distances to the demand points. In addition, this algorithm can be improved in the
interesting, important case where
1
:::
n
. In this situation the objective
function is globally convex and this fact can be exploited to reduce the enumeration
of the entire list of ordered regions. Indeed, if one optimal solution of any Problem
P
is interior to the ordered region O
or this solution cannot be improved in
adjacent regions then by global convexity this implies that it is the global minimum.
Otherwise, one can follow a descent iterative scheme moving from one region to
another one not previously visited. The above arguments justify the validity of the
following algorithm.
