Geoscience Reference
In-Depth Information
We also observe that the above problem simplifies for those cases where r is even.
In these cases, we can replace the constraints (
10.18
) by the simplest constraints
v
k`
D
.x
k
a
k`
/
r
;
8
k;`:
This reformulation reduces the degree of the polynomials defining the feasible set.
We illustrate the above formulation with a standard model in location analysis:
the k-centrum problem in the plane.
Example 10.2
Let us assume that we are given a set of demand points A
D
f
a
1
;:::;a
n
g
2
,wherea
i
D
.a
i1
;a
i2
/,fori
D
1;:::;n.Wewishtomodel
the k-centrum (k<n) with `
3
-distance, i.e. r
D
3 and s
D
1, with respect to the
demand points in A and a feasible region defined by a set
K
. It is clear that in this
case d
D
2, m
D
n and each function f
i
.x/
WDk
x
a
i
k
3
;i
D
1;:::;n.
According to the model above this problem can be formulated as follows:
R
X
n
X
n
minimize
u
i
w
ij
iD1
jDnkC1
X
n
w
ij
D
1;
for j
D
1;:::;n;
subject to
iD1
X
n
w
ij
D
1;
for j
D
1;:::;n;
iD1
X
n
X
n
w
ij
u
i
w
ij
C1
u
i
;j
D
1;:::;n
1
iD1
iD1
w
ij
w
ij
D
0;
for i;j
D
1;:::;n;
v
k`
D
.x
`
a
k`
/
6
;
k
D
1;:::;n; `
D
1;:::;2;
X
d
u
k
D
.
v
k`
/;
k
D
1;:::;n;
`D1
X
n
w
ij
1;
i
D
1;:::;n;
jD1
X
2
v
ij
M
6
;
i
D
1;:::;n;
jD1
w
ij
2
R
;
8
i;j
D
1;:::;m;
v
k`
0;
u
k
0;
k
D
1;:::;n;`
D
1;:::;d;
x
2
K
:
Next, we get a result that shows the equivalence between the above polynomial
optimization formulation and our location problem (
OMPF
).
