Geoscience Reference
In-Depth Information
Choose
x
o
as an appropriate starting point. Initialize
Algorithm 10.1
Step 1.
WD;
,
y
D
x
o
.
Step 2. Consider
O
o
which
y
belong to, where
o
determines the order.
Step 3. Solve the linear program
P
0
.Letu
0
D
.x
1
;x
2
;
z
0
/
be an optimal
solution. If
x
0
D
.x
1
;x
2
/
62
O
o
then let
O
o
be such that
x
0
2
O
o
and go
to Step
3
.
Step 4.
L
Let
y
o
D
.x
1
;x
2
/
.
If
y
o
belongs to the interior of
O
o
then set
y
D
y
0
and go to Step 8.
Step 5.
WDf
0
g
Step 7. If there exist
i
and
j
verifying
.y
o
a
i
/
D
.y
o
a
j
/
with
i<j
such
that
.
1
;:::;
j
;:::;
i
;:::;
n
/
62
If
F.y
o
/
ยค
F.y
/
then
Step 6.
L
then do
(a)
y
WD
y
o
,
o
WD
.
1
;
2
;:::;
j
;:::;
i
;:::;
n
/
(b)
L
[f
o
g
(c) gotoStep3
L
WD
L
else go to Step 8 (Optimum found)
Step 8.
Output
y
The above algorithm is efficient in the sense that it is polynomially bounded
in fixed dimension. Once the dimension of the problem is fixed, its complexity is
dominated by the complexity of solving a linear program for each ordered region.
Since the number of ordered regions is polynomially bounded, Algorithm
10.1
is
polynomial.
The nice geometry of the problem in the plane allows us to derive the two above
algorithms. Nevertheless, this geometry in higher dimension is rather intricate and
the above approach, based on building ordered regions, is very difficult since no
efficient algorithm for computing bisectors is available in dimension greater than 2.
In spite of that, we will present an alternative algorithm for solving the single
facility ordered median problem in any dimension d. To this for, we shall introduce
a valid MILP model that provides the optimal solution of the problem. Indeed,
consider the following set of binary variables
8
<
1 if the distance induced by facility i
goes in sorted position j
0 otherwise.
z
ij
WD
:
and the continuous variable
j
D
distance between a facility and its server in the j-th position in the ordered
sequence of distances between each facility and its corresponding server.
